D. Complete Tripartite

题链
与其他题解不同
我首先发现的是没有相连的一定是同一组
那么我们直接对于整个数组
遍历一遍 将与1同组的搞出来 要是下一个位置已经有组了 我们就继续
这样搞出来了几组
但是这些组仅仅是与他们的组最前面的是一样的
可能有个别与其他组的少一条边 与自己组的多一条边
这样是不合法的
我们只有组内的和“组长”是一样的才行
这里分组用的并查集

map<int,int>g[N];
int p[N];
int find(int x){
    if(p[x]!=x)p[x]=find(p[x]);
    return p[x];
}
void merge(int x, int y){
    p[find(x)] = find(y);
}
void solve(){
    int n,m;cin>>n>>m;
    for(int i=1;i<=m;i++){
        int u,v;cin>>u>>v;
        g[u][v]++;
        g[v][u]++;
    }
    for(int i=1;i<=n;i++)p[i]=i;
    int cnt=0;
    for(int i=1;i<=n;i++){
        if(p[i]==i){
            cnt++;
            if(cnt==4){
                cout<<-1<<endl;
                return;
            }
            for(int j=i+1;j<=n;j++){
                if(g[i].count(j) == 0) {
                    merge(j, i);
                    //这一步一共就是O（m）的
                    if(g[j]!=g[i]){
                        cout << -1 << endl;
                        return;
                    }
                }
            }
        }
    }
    set<int>s;
    for(int i=1;i<=n;i++){
        s.insert(p[i]);
    }
    if(s.size()!=3){
        cout<<-1<<endl;
    }else{
        map<int,int>mp;
        cnt=1;
        for(auto c:s)mp[c]=cnt++;
        for(int i=1;i<=n;i++){
            cout<<mp[p[i]]<<' ';
        }
    }
}