颜色团 - 题解

标签与难度

标签: 并查集, 图论, 启发式合并, 动态连通性, 数据结构, set 难度: 2500

题目大意喵~

你好呀，指挥官！这道题是关于一个带颜色的小世界的故事，喵~

我们有一张由 $n$ 个点和 $m$ 条边组成的无向图。每个点都有自己的颜色。

题目里定义了一种叫做【团】的东西。两个点 $a$ 和 $b$ 在同一个【团】里，当且仅当它们颜色相同，并且能通过一条只由这种颜色的点组成的路径互相到达。换句话说，一个【团】就是把所有相同颜色的点和它们之间的边拿出来，形成的一个个连通块，喵~

接下来会有 $q$ 次操作。每次操作会指定一个点 $x$ 和一个新的颜色 $c$。我们需要找到点 $x$ 所在的那个【团】，然后把这个【团】里所有点的颜色都变成 $c$。

每次操作结束后，小蓝想知道图里现在总共有多少个【团】。我们的任务就是帮帮他，告诉他答案，呐！

举个栗子：

• 假设有三个点 {1(红), 2(红), 3(蓝)}，边是 (1,2) 和 (2,3)。
• 一开始，点1和点2颜色相同且连通，所以它们组成一个红色【团】。点3自己是一个蓝色【团】。总共有2个团。
• 如果操作是 (2, 蓝)，点2所在的红色团 {1, 2} 都要变成蓝色。
• 现在点的颜色是 {1(蓝), 2(蓝), 3(蓝)}。因为 (1,2) 和 (2,3) 两条边存在，现在所有点都连通并且都是蓝色，它们组成了一个超大的蓝色【团】！总共就只有1个团了，喵~

解题思路分析

这道题的核心是动态地维护一群群颜色相同的连通块（也就是【团】），并且在颜色变化后，正确地合并或拆分它们。这听起来就很适合用我们的老朋友——并查集 (DSU) 来解决，的说！

1. 初步建模：用并查集表示【团】

我们可以把每个【团】看作并查集里的一个集合。集合的代表元（根节点）就代表这个【团】。并查集里集合的数量，就是我们要求的答案 total_cliques。

• 初始化：
  1. 最开始，每个点都是一个独立的【团】，所以我们有 $n$ 个团。total_cliques = n。
  2. 初始化并查集，让每个节点的父节点都是它自己。
  3. 我们还需要一个数组 clique_color[i] 来记录根节点 i 所代表的【团】的颜色。
  4. 遍历所有给定的 $m$ 条边 (u, v)。如果 color[u] 和 color[v] 相同，说明它们在同一个颜色的子图中是相连的，应该属于同一个【团】。我们就调用 union_sets(u, v) 来合并它们。每次成功合并，total_cliques 就减一。

经过初始化，我们就得到了图在最开始状态下的所有【团】了。

2. 核心挑战：处理颜色修改

当一个【团】（假设根是 root_x）的颜色从 c_old 变为 c_new 时，会发生什么呢？

clique_color[root_x] 更新为 c_new。更重要的是，这个【团】现在可能会和它的一些邻居【团】颜色变得相同了！如果 root_x 和它的一个邻居 root_y 都有了新颜色 c_new，它们之间只要有边相连，就应该合并成一个更大的【团】。

这里的瓶颈就来了：

• 如何快速找到一个【团】的所有邻居【团】？
• 合并两个【团】时，它们各自的邻居信息要怎么合并？

如果我们天真地在每次合并时，都遍历新【团】的所有节点，再遍历所有节点的边来更新邻居关系，那复杂度肯定会爆炸的，喵呜~ >_<

3. 进阶策略：维护【团】之间的邻接关系

我们需要在【团】的层面（也就是并查集的根节点层面）建立一个“邻接图”。

• 我们可以给每个【团】（根节点 r）维护一个邻居列表，比如 adj[r]，里面存放所有与 r 有边直接相连的其他【团】的根节点。
• 这个邻接图可以在初始化时，遍历所有跨越不同【团】的原始边 (u, v) 来建立。

但这样还是有合并的问题。当合并【团】u和v时，我们需要合并 adj[u] 和 adj[v]。简单地把一个列表加到另一个上，再更新所有相关邻居的反向链接，这个过程非常慢。

4. 最终绝招：启发式合并与度数分治

为了解决合并效率问题，我们可以请出两个强大的魔法：启发式合并 和一种巧妙的 度数分治 思想。这正是参考代码中那种非常聪明的做法的核心，喵~

这个想法是这样的：对于【团】u和v之间的一条“邻边”，我们不双向存储。而是根据某种规则，只存一条有向边。比如，我们规定，边总是从“小”的【团】指向“大”的【团】。这里的“大小”可以用【团】的邻居数量（即度数）来衡量。

1. 数据结构改造：

   • dsu_parent[]: 并查集。
   • clique_color[]: 记录每个【团】根节点的颜色。
   • clique_degree[]: 记录每个【团】的度数（邻居数量）。
   • outgoing_adj[u]: 一个 vector，存储 u 指向的度数更大或相等的邻居【团】。
   • incoming_adj_by_color[u]: 一个 set<pair<int, int>>。如果一个度数更小的邻居 v 指向 u，那么 u 就在这里记录下 v 的信息，格式是 {color_of_v, v}。使用 set 是为了能按颜色快速查找！

2. 工作流程：

   • 初始化：
     • 完成基础的 DSU 合并后，我们得到了初始的【团】和它们的颜色。
     • 构建【团】间邻接关系：遍历所有原始边 (u, v)，如果 find(u) != find(v)，得到两个【团】r_u 和 r_v。计算它们的度数，然后根据度数大小关系，在 outgoing_adj 和 incoming_adj_by_color 中添加记录。
   • 处理查询 (x, c_new)：
     1. 找到 x 所在【团】的根 root_x。
     2. c_old = clique_color[root_x]。如果 c_old == c_new，无事发生。
     3. 更新：首先，clique_color[root_x] 变为 c_new。然后，root_x 需要通知所有它指向的（度数大的）邻居，它的颜色变了。对于 outgoing_adj[root_x] 中的每个邻居 v，我们去 incoming_adj_by_color[v] 中删掉 {c_old, root_x}，再加入 {c_new, root_x}。
     4. 寻找合并对象：现在 root_x 的颜色是 c_new，它可能会和哪些邻居合并呢？
        • 度数大的邻居：遍历 outgoing_adj[root_x]，如果邻居 v 的颜色 clique_color[v] 也是 c_new，就合并 root_x 和 v。
        • 度数小的邻居：查询自己的 incoming_adj_by_color[root_x]，看有没有颜色为 c_new 的记录。set 的 lower_bound 可以高效地做到这一点！如果找到了，就合并它们。
     5. 合并操作 merge_cliques(u, v)：这是最复杂的部分，需要用到启发式合并。假设我们将度数小的 v 合并到度数大的 u 中。
        • 合并并查集。
        • 合并 incoming_adj_by_color：将 v 的 incoming_adj_by_color 中的所有元素，移动到 u 的里面。因为是 set，启发式合并（总是将小的合并到大的）的效率很高。
        • 合并 outgoing_adj：将 u 和 v 的 outgoing_adj 列表合并，并重新计算新【团】u 的邻居和度数，更新所有邻居的反向链接。这个过程比较繁琐，但因为我们总是在合并，图的边会越来越少，整体复杂度是可控的。

这个方法通过巧妙的非对称存储和启发式合并，把复杂度控制在了可以通过的范围内。是不是很神奇，喵~

代码实现

下面是我根据上面的思路，精心重构的一份代码。注释很详细，希望能帮助你理解每一步哦！

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
#include <set>

// 使用 pair<int, int> 来表示 {color, clique_root}
using ColorNodePair = std::pair<int, int>;

const int MAXN = 100005;

// --- 并查集 (DSU) ---
int parent[MAXN];
int find_set(int v) {
    if (v == parent[v]) {
        return v;
    }
    return parent[v] = find_set(parent[v]);
}

// --- 团的数据结构 ---
int clique_color[MAXN];
int clique_degree[MAXN]; // 记录一个团的邻居数量
std::vector<int> outgoing_adj[MAXN]; // 度数小的团指向度数大的团
std::set<ColorNodePair> incoming_adj_by_color[MAXN]; // 度数大的团记录来自度数小的团的信息

int total_cliques;

// 合并两个团，这是核心操作
void merge_cliques(int u, int v) {
    u = find_set(u);
    v = find_set(v);
    if (u == v) return;

    // 启发式合并：总是将度数小的合并到度数大的
    if (clique_degree[u] < clique_degree[v]) {
        std::swap(u, v);
    }

    // 1. 从各自邻居的 incoming set 中移除即将被合并的团的信息
    for (int neighbor : outgoing_adj[u]) {
        incoming_adj_by_color[neighbor].erase({clique_color[u], u});
    }
    for (int neighbor : outgoing_adj[v]) {
        incoming_adj_by_color[neighbor].erase({clique_color[v], v});
    }
    
    // 2. 将 v 的 incoming 信息合并到 u
    // 启发式合并 set
    if (incoming_adj_by_color[u].size() < incoming_adj_by_color[v].size()) {
        swap(incoming_adj_by_color[u], incoming_adj_by_color[v]);
    }
    for (const auto& p : incoming_adj_by_color[v]) {
        // p.second 是 v 的一个小邻居，现在它成了 u 的小邻居
        // 需要更新这个小邻居的 outgoing_adj
        int small_neighbor = p.second;
        // 找到指向 v 的边并改为指向 u
        for (int& out_neighbor : outgoing_adj[small_neighbor]) {
            if (out_neighbor == v) {
                out_neighbor = u;
                break;
            }
        }
        incoming_adj_by_color[u].insert({p.first, small_neighbor});
    }
    incoming_adj_by_color[v].clear();


    // 3. DSU 合并
    parent[v] = u;
    total_cliques--;

    // 4. 合并邻接关系并重建
    std::vector<int> merged_neighbors;
    std::vector<bool> visited(MAXN + 1, false);

    auto add_neighbors = [&](int node) {
        for (int neighbor : outgoing_adj[node]) {
            if (!visited[neighbor]) {
                merged_neighbors.push_back(neighbor);
                visited[neighbor] = true;
            }
        }
        for (const auto& p : incoming_adj_by_color[node]) {
            int neighbor = p.second;
            if (!visited[neighbor]) {
                merged_neighbors.push_back(neighbor);
                visited[neighbor] = true;
            }
        }
    };
    
    add_neighbors(u);
    add_neighbors(v);

    outgoing_adj[u].clear();
    outgoing_adj[v].clear();
    clique_degree[u] = 0;
    
    for (int neighbor : merged_neighbors) {
        if (neighbor == u || neighbor == v) continue;
        clique_degree[u]++;
        clique_degree[neighbor]--; // 它原来和u,v的连接现在只有一个了
        
        // 重新确定边的方向
        if (clique_degree[u] > clique_degree[neighbor]) {
            outgoing_adj[neighbor].push_back(u);
        } else {
            outgoing_adj[u].push_back(neighbor);
        }
    }
    
    // 5. 更新所有新邻居的 incoming set
    clique_color[u] = clique_color[v]; // 保证颜色一致
    for(int neighbor : outgoing_adj[u]){
        incoming_adj_by_color[neighbor].insert({clique_color[u], u});
    }
    for(const auto& p : incoming_adj_by_color[u]){
        int neighbor = p.second;
        clique_degree[neighbor]++; // 度数恢复
        for(int& out_neighbor : outgoing_adj[neighbor]){
            if(out_neighbor == u || out_neighbor == v){
                out_neighbor = u;
                break;
            }
        }
    }
}


int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n, m, q;
    std::cin >> n >> m >> q;

    total_cliques = n;
    for (int i = 1; i <= n; ++i) {
        parent[i] = i;
        std::cin >> clique_color[i];
    }

    std::vector<std::pair<int, int>> edges;
    for (int i = 0; i < m; ++i) {
        int u, v;
        std::cin >> u >> v;
        edges.push_back({u, v});
        if (clique_color[u] == clique_color[v]) {
            int root_u = find_set(u);
            int root_v = find_set(v);
            if (root_u != root_v) {
                parent[root_v] = root_u;
                total_cliques--;
            }
        }
    }
    
    // 重新整理颜色到根节点
    for (int i = 1; i <= n; ++i) {
        clique_color[find_set(i)] = clique_color[i];
    }

    // 构建团图和度数
    std::vector<std::vector<int>> temp_adj(n + 1);
    for (const auto& edge : edges) {
        int r_u = find_set(edge.first);
        int r_v = find_set(edge.second);
        if (r_u != r_v) {
            temp_adj[r_u].push_back(r_v);
            temp_adj[r_v].push_back(r_u);
        }
    }

    for (int i = 1; i <= n; ++i) {
        if (parent[i] == i) {
            std::sort(temp_adj[i].begin(), temp_adj[i].end());
            temp_adj[i].erase(std::unique(temp_adj[i].begin(), temp_adj[i].end()), temp_adj[i].end());
            clique_degree[i] = temp_adj[i].size();
        }
    }

    // 根据度数建立非对称邻接关系
    for (int i = 1; i <= n; ++i) {
        if (parent[i] == i) {
            for (int neighbor : temp_adj[i]) {
                if (clique_degree[i] < clique_degree[neighbor] || (clique_degree[i] == clique_degree[neighbor] && i < neighbor)) {
                    outgoing_adj[i].push_back(neighbor);
                    incoming_adj_by_color[neighbor].insert({clique_color[i], i});
                }
            }
        }
    }

    while (q--) {
        int x_node, c_new;
        std::cin >> x_node >> c_new;

        int root_x = find_set(x_node);
        int c_old = clique_color[root_x];

        if (c_old == c_new) {
            std::cout << total_cliques << "\n";
            continue;
        }

        // 更新颜色，并通知度数大的邻居
        for (int neighbor : outgoing_adj[root_x]) {
            incoming_adj_by_color[neighbor].erase({c_old, root_x});
            incoming_adj_by_color[neighbor].insert({c_new, root_x});
        }
        clique_color[root_x] = c_new;

        // 寻找并合并
        std::vector<int> to_merge;
        // 从度数大的邻居中找
        for (int neighbor : outgoing_adj[root_x]) {
            if (clique_color[neighbor] == c_new) {
                to_merge.push_back(neighbor);
            }
        }
        // 从度数小的邻居中找
        auto it_start = incoming_adj_by_color[root_x].lower_bound({c_new, 0});
        auto it_end = incoming_adj_by_color[root_x].lower_bound({c_new + 1, 0});
        for (auto it = it_start; it != it_end; ++it) {
            to_merge.push_back(it->second);
        }
        
        for (int neighbor_root : to_merge) {
            merge_cliques(root_x, neighbor_root);
            root_x = find_set(root_x); // root_x可能在合并中被改变
        }
        
        std::cout << total_cliques << "\n";
    }

    return 0;
}

注意: 上述代码是一个尝试性的重构，旨在清晰地展示思路。实际比赛中，merge_cliques 函数的实现细节非常微妙，容易出错。参考代码中的实现经过了充分的测试，虽然紧凑但非常高效。我的代码在合并邻居关系时为了清晰性采取了比较直白的方式，可能在某些极端情况下效率不如原版，但核心思想是一致的，喵~

复杂度分析

• 时间复杂度: $O((M+Q) \log N \cdot \alpha(N))$ 或类似的形式。

  • 初始化并查集和建图是 $O(M \alpha(N) + M \log M)$。$\alpha(N)$ 是并查集的反阿克曼函数，近乎常数。
  • 每次查询，颜色更新和查找合并对象都比较快。
  • 复杂度的主要来源是 merge_cliques 操作。由于我们采用了启发式合并（按度数大小），一个【团】的邻居信息在多次合并中，每个元素被移动的总次数是对数级别的。set 的操作是 $O(\log k)$ 的。综合起来，整个算法的均摊复杂度是高效的，能够通过本题的数据范围。

• 空间复杂度: $O(N+M)$

  • parent, clique_color, clique_degree 等数组都是 $O(N)$。
  • 邻接关系 outgoing_adj 和 incoming_adj_by_color 在最坏情况下总共存储 $O(M)$ 条【团】间边信息。所以空间复杂度是线性的。

知识点总结

1. 并查集 (DSU): 解决动态连通性问题的利器，非常适合用来表示和维护【团】这样的集合。
2. 启发式合并 (Merge Small to Large): 在合并两个数据结构（如 set 或 vector）时，总是将小的合并到大的里面，可以大大优化总时间复杂度。这是处理这类动态图问题的关键技巧之一。
3. 度数分治/非对称存储: 为了避免在合并时双向更新邻居关系带来的巨大开销，我们将【团】间的边定义为有向的（从度数小指向度数大）。这使得更新操作变得局部化，大大提高了效率。
4. std::set 的妙用: set 不仅能自动去重和排序，它的 lower_bound 方法还能帮助我们快速查找特定范围的元素，非常适合用在 incoming_adj_by_color 中按颜色查找邻居。

这道题是并查集应用的进阶，综合了多种数据结构和算法思想，是一道非常好的练习题，喵~ 希望我的题解能帮到你！