（抄知识点方便自己复习）//摘自俞勇的acm国际大学生程序设计竞赛，知识与入门
基本概念
不相交集为一组彼此不相交（没有公共元素）的集合。并查集算法作用于一个不相交集，实际应用中可以在近乎常数的时间内完成下列两种操作。
1：查找（find）：确定元素所在的集合。一般用来判断两个元素是否在同一个集合。
2：合并（Union）：将两个集合合并成一个集合。
对于查找操作，假设需要确定x所在的集合，也就是确定集合的代表元。可以沿着parent【x】不断在树形结构中向上移动，直到到达根节点，根节点即代表元。
判断两个元素是否属于同一个集合，只需看他们的代表元是否相同即可。为了加快速度，每次查找操作的过程中，可以将x到根节点路径上的所有点的parent设为根节点，
这样下次再次查找时就不必再沿着路径一步步寻找了，该优化方法为压缩路径。
//hdu1988 带权并查集
#include <iostream> using namespace std; const int maxn=30005; int fa[maxn],d[maxn],s[maxn]; int find(int x){ if(fa[x]==x) return x;//若是根节点就直接返回 int t=fa[x];//否则记录点x的当前根节点。 fa[x]=find(fa[x]);//更新元。 d[x]+=d[t];//将其父节点的深度跟新跟x; return fa[x]; } void Move(int x,int y){ x=find(x),y=find(y);//找到对应的元 fa[x]=y;//跟新x的根节点 d[x]+=s[y];//更新其x的深度，y的树的大小，x树的大小。 s[y]+=s[x]; s[x]=0; } int main() { for(int i=0;i<maxn;i++){ fa[i]=i; s[i]=1; d[i]=0; } int p; cin>>p; while(p--){ char str[1];int a[2]; cin>>str[0]; if(str[0]=='M'){ cin>>a[0]>>a[1]; Move(a[0],a[1]); } if(str[0]=='C'){ cin>>a[0]; find(a[0]); cout<<d[a[0]]<<endl; } } //cout << "Hello world!" << endl; return 0; }
hdu 2492
http://blog.csdn.net/lxmky/article/details/7654916#//摘自
#include <iostream> #include <cstring> using namespace std; const int maxn=5005; int f[maxn],relations[maxn]; int find(int x){ int temp=f[x]; if(f[x]==x) return x; x=find(temp); relations[x]=(relations[x]+relations[f[temp]])%2; return f[x]; } void unionset(int a,int b){ int x=find(a);int y=find(b); if(x==y) return ; f[x]=y; relations[x]=(relations[a]-relations[b]+1)%2; return ; } int main() { int t,count=1; cin>>t; while(t--){ int n,m; cin>>n>>m; memset(relations,0,sizeof(relations)); for(int i=1;i<=n;i++){ f[i]=1; } int flag = 1; for(int i = 0; i < m; i++) { int tmp1,tmp2; cin>>tmp1>>tmp2; if(find(tmp1) == find(tmp2)) { if(relations[tmp1] != (relations[tmp2] + 1) % 2) //如果不满足异性关系，有矛盾 flag = 0; } else { unionset(tmp1, tmp2); } } if(flag) { cout<<"Scenario #"<<count<<":"<<endl<<"No suspicious bugs found!"<<endl<<endl; } else { cout<<"Scenario #"<<count<<":"<<endl<<"Suspicious bugs found!"<<endl<<endl; } } //cout << "Hello world!" << endl; return 0; }
