POJ 1703 并查集的应用 关系并查集l两种方法

/***************** 有两个帮派，有两种操作 D a b表示a 和 b不是一个帮派；A a b 表示询问a b是否是一个帮派， 若至此还不确定，输出“Not sure yet”。 思路： 关系并查集；只要两者的关系确定了，就将他们放入同一个集合内，而另外增加一个表示关系的数组r[ ]来表示该节点与其父亲的关系。0表示同一类，1表示不同类。 初始时集合只有自己一个元素，r[ ]设置为0。 通过Find(int x) 来更新每个节点与新的父节点之间的关系 通过Union() 来更新父节点 （即两个集合进行合并），来确定被更新的父节点作为子节点与 现在父节点之间的关系。 ******************/ #include<iostream> #include<cstring> #include<cstdio> #include<algorithm> #include<cmath> #include<map> #define LL long long #define INF 0x3f3f3f3f using namespace std; const int N=110000; int bin[N]; int ran[N]; void init(int n){ for(int i=0;i<=n;i++){ bin[i]=i; ran[i]=0 ; ///表示和根节点是同一个集合的 } } int Find(int x){ if(bin[x]!=x){ int fa=bin[x]; bin[x]=Find(bin[x]);///最最原始的根一定是ran[fa]==0; ran[x]=(ran[x]+ran[fa])%2; /// 由已知根的关系 推出后代的关系 } return bin[x]; } void Union(int x,int y){ int fx=Find(x); int fy=Find(y); if(fx!=fy){ bin[fx]=fy; /// 已经知道x与y的关系是 不同集合关系 /// ran[x]记录的是与fx的关系, ran[y]记录的是与fy的关系 ///由这两个关系推出fx与 根fy的关系 ran[fx]=(ran[x]+ran[y]+1)%2; ///自己模拟一下 } } int main(){ int t,n,m,u,v; char s[10]; scanf("%d",&t); while(t--){ scanf("%d%d",&n,&m); init(n); for(int i=1;i<=m;i++){ scanf("%s%d%d",s,&u,&v); if(s[0]=='A'){ if(Find(u)==Find(v)){ ///对后代与根的关系进行了更新 if(ran[u]==ran[v]){ puts("In the same gang."); } else puts("In different gangs."); } else puts("Not sure yet."); } else Union(u,v); } } return 0; } 方法二 <pre name="code" class="cpp">/***************** ******************/ #include<iostream> #include<cstring> #include<cstdio> #include<algorithm> #include<cmath> #include<map> #define LL long long #define INF 0x3f3f3f3f using namespace std; const int N=110000; int bin[2*N]; int ran[N]; int Find(int x){ return bin[x]==x?x:bin[x]=Find(bin[x]); } void Union(int x,int y){ int fx=Find(x); int fy=Find(y); if(fx!=fy){ bin[fx]=fy; } } int main(){ int t,u,v,n,m; char s[10]; scanf("%d",&t); while(t--){ scanf("%d%d",&n,&m); for(int i=0;i<=2*n;i++){ bin[i]=i; } while(m--){ scanf("%s%d%d",s,&u,&v); if(s[0]=='D'){ Union(u,v+n); Union(u+n,v); } else{ if(Find(u)==Find(v)){ ///三个关系之间存在相反的相反关系，那就是相等 puts("In the same gang."); } else if(Find(u+n)==Find(v)){///||Find(u)==Find(v+n); puts("In different gangs."); } else puts("Not sure yet."); } } } }