CF1228D Complete Tripartite

有些题解够了，这题和三分图的判定没有什么关系……

这里主要是一个转化，一个点会和所以不与自己相连的点处于相同的集合中。

换句话说，如果两个点在同一个集合内，那与这两个点相连的点的集合是完全相同的。

这里使用了哈希来判定，另外，如果有孤立的点存在，则要特判。

const int maxN=1e5+10;
vector<int> g[maxN];
int n,m;
pll hsh[maxN];
int col[maxN];

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0); 
	n=rd(),m=rd();
	fp(i,1,m){
		int u=rd(),v=rd();
		g[u].eb(v),g[v].eb(u);
	}
	fp(i,1,n){
		if(g[i].empty()){
			cout << "-1" << endl;
			return 0;
		}
	}
	fp(i,1,n)
		sort(g[i].begin(),g[i].end());
	fp(i,1,n){
		hsh[i].second=i;
		for(int x:g[i])
			hsh[i].first=(hsh[i].first*base+x)%mod;
	}
	sort(hsh+1,hsh+n+1);
	vector<int> v;
	fp(i,2,n)
		if(hsh[i].first!=hsh[i-1].first) v.eb(i);
	if(v.size()!=2){
		cout << "-1" << endl;
		return 0;
	}
	fp(i,1,v[0]-1)
		col[hsh[i].second]=1;
	fp(i,v[0],v[1]-1)
		col[hsh[i].second]=2;
	fp(i,v[1],n)
		col[hsh[i].second]=3;
	fp(i,1,n) cout << col[i] << ' ';
	cout << endl;
	
	return 0;
}