题解：P6279 [USACO20OPEN] Favorite Colors G

梦见云月 · 2026-10-26 10:06:41 · 题解

题目要求是，只要一个点有至少两个出点，就要把这两个出点合并。

并查集合并是好做的，但是染色似乎有些不好想。

因此考虑启发式合并，除了合并点，还要把边继承过去。

然后就是暴力模拟上述过程了，不必赘述。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m;
int siz[1000005];
int fa[1000005];
int col[1000005];
int vis[1000005];
int id;
vector<int>p[1000005];
vector<int>vec[1000005]; 
queue<int>q;

inline void merge(int x,int y){
    if(p[x].size()<p[y].size()){
        swap(x,y);
    }
    for (int i=0;i<vec[y].size();i++){
        int v=vec[y][i];
        vec[x].push_back(v);
    }
    for (int i=0;i<p[y].size();i++){
        int v=p[y][i];
        fa[v]=x;
        p[x].push_back(v);
    }
    if (vec[x].size()>1){
        q.push(x);
    }
    return;
}

signed main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int x,y;
        cin>>x>>y;
        vec[x].push_back(y);
    }
    for(int i=1;i<=n;i++){
        fa[i]=i;
        if(vec[i].size()>1){
            q.push(i);
        }
        p[i].push_back(i);
    }
    while(q.size()){
        int x=q.front();
        q.pop();
        while(vec[x].size()>1){
            int a=fa[vec[x][0]];
            int b=fa[vec[x][1]];
            vec[x].erase(vec[x].begin());
            if(a!=b){
                merge(a,b);
            }
        }
    }
    for(int i=1;i<=n;i++){
        if(!col[fa[i]]){
            col[fa[i]]=++id;
        }
        cout<<col[fa[i]]<<'\n';
    }
    return 0;
}