[CF1228D] Complete Tripartite

给定一张图，判定它是否是完全三分图。

Solution

考虑到最终划分到同一集合中的点，它们的直接可达点都是相同的

于是我们记录每个点的直接可达点集合，排序，然后分段

如果不是三段，则不存在

同时要预先筛去有孤立点的情况

#include <bits/stdc++.h>
using namespace std;

#define int long long
const int N = 1000005;

struct item {
    basic_string <int> str;
    int id;

    bool operator < (const item &b) const {
        return str < b.str;
    }
} a[N];

int n,m,t1,t2,t3,c[N],d[N];

signed main() {
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1;i<=m;i++) {
        cin>>t1>>t2;
        a[t1].str+=t2;
        a[t2].str+=t1;
    }
    for(int i=1;i<=n;i++) {
        a[i].id=i;
        sort(a[i].str.begin(),a[i].str.end());
    }
    sort(a+1,a+n+1);
    if(a[1].str.length()==1) {
        cout<<-1;
        return 0;
    }
    for(int i=1;i<=n;i++) {
        if(a[i].str==a[i-1].str) {
            c[i]=c[i-1];
        }
        else {
            c[i]=c[i-1]+1;
        }
    }
    if(c[n]!=3) {
        cout<<-1;
        return 0;
    }
    for(int i=1;i<=n;i++) if(c[i]==0) {cout<<-1; return 0;}
    for(int i=1;i<=n;i++) d[a[i].id]=c[i];
    for(int i=1;i<=n;i++) cout<<d[i]<<" ";
}