题意：t组样例，n个宗教，m条信息。D[a][b]表示a、b属于不同宗教，A[a][b]需要自己判断，若a、b属于同一宗教输出In the same gang.，若a、b属于不同宗教输出In the different gangs.，若无法确定a、b的情况则输出Not sure yet.
解题思路：并查集.与食物链那道题类似，关键点都在于如何维护不同集合间的关系，而并查集的功能是维护相同集合间的关系，要想用并查集维护不同集合间的关系就要改变集合元素，原本unit(a,b)表示a、b属于同一集合，现在用unit(a,b+n)表示a、b+n属于相同集合，那么a、b就属于不同集合，a属于第一个集合，b属于第二个集合，同理unit(a+n,b)表示a属于第二个集合，b属于第一个集合。每次进行D操作时，将所有可能都unit。注意并查集的功能是维护相同集合间的关系
这道题不能用cin读入cout输出，会超时...，改用scanf读入printf输出就不会超时。事实证明使用scanf、printf的速度比cin、cout快多了...
注意getchar()的使用，因为读入整数又读入字符，不用getchar()的话就会把回车当作字符读进去
代码：
#include <iostream> #include <algorithm> #include <cstring> #include <string> #include <cmath> #include <cstdio> using namespace std; const int maxn=1e5+10; int t,n,m; int par[maxn*2],rank[maxn*2]; void init() { for(int i=0;i<n*2;i++) { par[i]=i; rank[i]=0; } } int find(int x) { if(x==par[x])return x; else { return par[x]=find(par[x]); } } void unit(int x,int y) { x=find(x),y=find(y); if(x==y)return ; if(rank[x]<rank[y])par[x]=y; else { par[y]=x; if(rank[x]==rank[y])rank[x]++; } } bool same(int x,int y) { return find(x)==find(y); } int main() { int t; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&m); getchar();//吃回车 init(); for(int i=0;i<m;i++) { char ch; int a,b; scanf("%c%d%d",&ch,&a,&b); getchar();//吃回车 if(ch=='D')//不同类 { unit(a,b+n); unit(a+n,b); } else if(ch=='A') { if(same(a,b+n)||same(a+n,b))printf("In different gangs.\n"); else if(same(a,b)||same(a+n,b+n))printf("In the same gang.\n"); else printf("Not sure yet.\n"); } } } return 0; }
