Favorite Colors (USACO Gold 2020 US Open)

这是一个思想简单，但是实现细节比较多的图和DSU的题。

题目表述比较绕，但关键就一句话：“如果奶牛xx和yy都仰慕一头喜欢颜色cc的奶牛，那么xx和yy喜欢的颜色相同。”，我们把(a,b)(a,b)表示成a→ba \rightarrow b的边，则上面的话的意思就是同样的颜色的牛（可以是同一头，也可能是不同的牛，假设颜色是cc）的所有出度指向的节点，颜色互相是一样的（假设为dd）。

读完题之后，解题方向应该是比较容易搞清楚的，从出度大于二的点开始往外遍历，孩子的颜色互相是一样的，然后这些孩子的孩子颜色全都是一样的。所以比较直观可以想到，这样的颜色分类的关系可以用并查集来表示，最后每个集合一个颜色，就是最大化颜色的数量了。要字母序也比较容易，从节点编号从小到大分配颜色就可以了。计算过程的话，大致上我们应该有一个queue来保存还没有处理过的节点，然后从里面不断取节点出来处理就行。

这里我们碰到一个问题，就是怎样保证我们不重复访问节点和边过多次，以至于超时。这里一个比较方便的trick，就是直接在图上合并节点，然后保证被合并的节点，只有一个加到工作队列中，这个节点就代表了所有的孩子（或者孩子的孩子...）。这样的话，就能保证每个节点被访问的次数最多一次，最后是O(Nlog⁡N)\mathcal{O}(N \log N)。如果不知道这个trick，题目还是比较麻烦的，可能会想出各种奇怪的写法，和碰以各种奇特的问题。

具体办法如下：

  1. 将所有出度大于1的节点加到工作队列。
  2. 从工作队列取一个节点，将所有孩子相邻两两用并查集合并，并将adjacency list也合并，最后只剩下一个孩子。
  3. 如果这个孩子的出度大于1，则加入工作队列中。
  4. 在合并的过程中，顺序是把数量小的adjacency list合并到大的，这样复杂度不会变成N2N^2。
  5. 题目有个坑是“自环”，在一些写法下，自环会带来不少麻烦，比如如果代码删除节点，那可能导致把当前节点删除而出错。上面的写法没有删除节点，所以可以直接通过有自环的点（至少包括测试点2）。

这里我们用set来保证adjacency list，合并起来比较方便，用vector也是可以的，很多其它解都是用vector。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
 
int n, m;
const int MAXN=200005;
set<int> g[MAXN];
int fa[MAXN];
int cl[MAXN];
queue<int> q;
 
int find(int x) {
    if (x == fa[x])
        return x;
    else
        return fa[x] = find(fa[x]);
}
 
void merge(int x, int y) {      // merge y into x
    x = find(x); y = find(y);
    if (x != y) {
        fa[y] = x;
        for (int u: g[y])       // merge adjacency list of y into x
            g[x].insert(u);
        if (g[x].size() > 1)    // add to work queue if needed
            q.push(x);
    }
}
 
int main() {
    scanf("%d %d", &n, &m);
    for (int i = 0; i < m; i++) {
        int u,v;
        scanf("%d %d", &u, &v);
        u--, v--;
        g[u].insert(v);
    }
    for (int i = 0; i < n; i++) {
        if (g[i].size() > 1)
            q.push(i);
        fa[i] = i;
    }
    while (q.size()) {
        int i = q.front();
        q.pop();
        while (g[i].size() > 1) {          // merge adjacency list of g[i]'s children
            int x = *g[i].begin();
            int y = *next(g[i].begin());
            g[i].erase(g[i].begin());
            merge(x, y);
        }
    }
    int c = 1;
    for (int i = 0; i < n; i++) {
        if (cl[i] > 0) continue;
        int u = find(i);
        if (cl[u] > 0) cl[i] = cl[u];
        else {
            cl[i] = cl[u] = c;
            c++;
        }
    }
    for (int i = 0; i < n; i++)
        printf("%d\n", cl[i]);
    return 0;
}