CodeForces1228D - Complete Tripartite 题解

这哈希长见识了。

这个是在CF 题解的评论区里看到的解法，非常震惊，不禁想到了学长和我们说过的话：“哈希是一种思想”。这次真的是体会到了。

思路：定义给了这么多，其实就是把完全二分图的概念扩展成了完全三分图。有一点很重要的性质，就是如果两个点的直接连接的点是一样的话那么这两个点必定属于同一个集合，这样就可以用哈希的方法快速判断两个点是否具有相同的邻居：通过 $pow_i=pow_{i-1}*p_1 \bmod p_2$ 给每个点一个值，那么一个点的哈希值就是该点邻居的点 $pow$ 值的和，如果两个点的哈希值一样，那么就大概率肯定两个点的邻居是一样的。

代码

#include <iostream>
#include <map>
 
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define fore(i, l, r) for (int i = (int)(l); i <= (int)(r); ++i)
#define ford(i, n) for (int i = (int)(n)-1; i >= 0; --i)
#define pb push_back
#define ms(a, x) memset(a, x, sizeof(a))
#define endl '\n'
using namespace std;
 
typedef long long ll;
const int INF = 0x3f3f3f3f;
typedef pair<int, int> pii;
 
const int N=1e5+5;
ll po[N],ha[N];
const int mod=1e9+7; 
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
    int n,m;
    cin>>n>>m;
    po[0]=1;
    for1(i,n) po[i]=po[i-1]*29;
    forn(i,m){
        int x,y;
        cin>>x>>y;
        ha[x]+=po[y];
        ha[y]+=po[x];
    }
    map<ll,ll> mp;
    int idx=0;
    for1(i,n){
        if(ha[i]==0){
            cout<<-1;
            return 0;
        }
        if(mp[ha[i]]==0) mp[ha[i]]=++idx;
    }
    if(idx==3){
        for1(i,n) cout<<mp[ha[i]]<<' ';
    }else cout<<-1;
  return 0;
}