题目大意：警察抓获N个罪犯，这些罪犯只可能属于两个团伙中的一个，现在给出M个条件（D a b表示a和b不在同一团伙）， 对于每一个询问(A a b)确定a，b是不是属于同一团伙或者不能确定。 这道题我用了两个并查集，把每个罪犯复制出两个来。一个是原来的，一个对称后的，以判断a b的相对团伙。 同一个集合表示可以有一个罪犯所述团伙推出其他罪犯所属团伙，用于判断是否能确定。 出于本人奇怪的性格，数据不上50万都懒得用Rank合并== 代码：
/* Time:329ms memory:944K*/include<cstdio>#include<cstring>using namespace std;#define N 200010int t,n,m,a,b,fa[N];int root(int x){ return fa[x]?fa[x]=root(fa[x]):x;}inline bool alk(int x,int y){ return root(x)==root(y);}inline void unite(int x,int y){ x=root(x); y=root(y); if(x!=y) fa[x]=y;}int main(){ scanf("%d",&t); while(t--){ memset(fa,0,sizeof(fa)); scanf("%d%d%*c",&n,&m); while(m--){ char c=getchar(); scanf("%d%d%*c",&a,&b); if(c=='D'){ unite(a,b+n); unite(a+n,b); } else puts(alk(a,b)?"In the same gang.":alk(a,b+n)?"In different gangs.":"Not sure yet."); } }}新闻热点
疑难解答
