HDU 6109 数据分割（并查集+set维护）

#include <bits/stdc++.h>
using namespace std;
const int maxn=100005;
int f[maxn],a[maxn],b[maxn],e[maxn];
set<int> G[maxn];
vector<int> ans;
int n;
int fa(int x)
{
	return f[x]==x?x:f[x]=fa(f[x]);
}
void init()
{
	for(int i=0;i<n;i++)
	 	f[i]=i,G[i].clear(); 
}
void solve()
{
	int cnt=0;
	for(int i=0;i<n;i++)
		{
			cnt++;
			int x=fa(a[i]),y=fa(b[i]);
			if(e[i])//a==b
			{
				if(x==y)continue;
				else
				{
					if(G[x].find(y)!=G[x].end())//a==b x!=y 相等不在一个集合 
					//集合之间有边   矛盾 
					{
						ans.push_back(cnt);
						cnt=0;
						init();
					}else//集合无边 并查集合并 
					{
						set<int>::iterator it;
						for(it=G[x].begin();it!=G[x].end();it++)
							{//连接x集合的边都删除 连接y 
								G[y].insert(*it);
								G[*it].erase(x);
								G[*it].insert(y);
							}
						G[x].clear();
						f[x]=y;//合并集合 x,y 
					}
				} 
				
			}
			else//a!=b 
			{
				if(x==y)//不相等的数在一个集合 矛盾 
				{
					ans.push_back(cnt);
					cnt=0;
					init();
				}else//不在一个集合  两个集合加一条边 
				{
					G[x].insert(y),G[y].insert(x);
				}
			}
		}
}
int main()
{
	scanf("%d",&n);
	for(int i=0;i<n;i++)scanf("%d %d %d",&a[i],&b[i],&e[i]);
	
	init();
			
	solve();
	int sz=ans.size();
	printf("%d\n",sz);
	for(int i=0;i<sz;i++)
		printf("%d\n",ans[i]);
	return 0;
}