题目链接:http://poj.org/problem?id=1703
http://poj.org/problem?id=1182
比较明显的并查集,也是并查集的深层应用,这两个题除了维护结点的集合外,另外维护结点到其父节点的向量,根据向量值来判断关系。
Code:
1703
#include<stdio.h> #include<stdlib.h> #define M 100008 int set[M]; int vec[M]; int n,m; char list[][24]={"Not sure yet.","In different gangs.","In the same gang."}; void Init() { int i; for(i=0;i<=n;i++) set[i]=i,vec[i]=0; } int Set(int r) { int t; if(r!=set[r]){ t=Set(set[r]); vec[r]=vec[r]^vec[set[r]]; set[r]=t; } return set[r]; } int Query(int x,int y) { int a=Set(x); int b=Set(y); if(a==b) return (vec[x]^vec[y])?1:2; return 0; } void Updata(int x,int y) { int a=Set(x); int b=Set(y); set[a]=b; vec[a]=1^vec[x]^vec[y]; } int main() { int t; int a,b; char op[2]; scanf("%d",&t); while(t--){ scanf("%d%d",&n,&m); Init(); while(m--){ scanf("%s%d%d",op,&a,&b); switch(op[0]){ case 'A':puts(list[Query(a,b)]);break; case 'D':Updata(a,b);break; } } } return 0; }