题解：洛谷P6279 [USACO20OPEN] Favorite Colors G

洛谷

被for(auto a:b)背刺了/fn/fn

---

思路

使用并查集和启发式合并

由题意我们可以很显然地发现一个节点的子节点颜色一样，同理，这些子节点的所有子节点颜色都一样，这时，我们可以把这些子节点全部合并到一个节点上，为降低复杂度，我们找到子节点最多的节点，把所有同深度的子树放到这个节点上。

对于每一棵树，我们给所有节点设定同一个颜色即可。

代码

#include<bits/stdc++.h>

using namespace std;

#define ll long long

const ll N=200005;

ll n,m;
vector<ll> e[N];
ll par[N];
ll cn[N];

ll find(ll x)
{
	return par[x]==x?x:par[x]=find(par[x]);
}

void dfs(ll x)
{
	ll hvs=e[x][0],mx=e[hvs].size();
    //size可能不是ll型的，不知道是不是必须转，但是如果把mx赋成-1就得转，否则会RE
	for(auto y:e[x])
	{
		if((ll)e[y].size()>mx) 
		{
			hvs=y;
			mx=(ll)e[hvs].size();
		}
	}
	
	ll mxf=find(hvs);
//	for(auto y:e[x]) //就是被这个东西背刺的，原因可能是e[x]后面会push新的节点进去，或者被clear，会导致错误
	for(ll i=0;i<(ll)e[x].size();i++)
	{
		ll y=e[x][i];
		ll yf=find(y);
		if(yf!=mxf)
		{
			par[yf]=mxf;
			for(auto k:e[yf])
			{
				e[mxf].push_back(k);
			}
			e[yf].clear();
		}
	}
	
	e[x].clear();
	e[x].push_back(mxf);
	
	if(e[mxf].size()>1)
	{
		dfs(mxf);
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);

	cin>>n>>m;
	for(ll i=1;i<=m;i++)
	{
		ll x,y;
		cin>>x>>y;
		e[x].push_back(y);
	}
	
	for(ll i=1;i<=n;i++)
	{
		par[i]=i;
	}
	
	for(ll i=1;i<=n;i++)
	{
		if(e[i].size()>1)
		{
			dfs(i);
		}
	}
	
	ll tot=0;
	for(ll i=1;i<=n;i++)
	{
		ll f=find(i);
		if(!cn[f])
		{
			cn[f]=++tot;
		}
		cout<<cn[f]<<"\n";
	}
	
	return 0;
}

---

Finished…