本文共 1521 字，大约阅读时间需要 5 分钟。
题意：一个城市n个犯罪嫌疑人，编号1-n，每次输入D x y表示x y属于同一帮派，A x y询问x y是否同一帮派或者不确定。
带权、种类并查集裸题，图片质量不好还请见谅。。oet[fx] = (oet[y]-oet[x]+d+2)%2 根据箭头关系就可以得出这个式子了，，加2是防止出现负值
#include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std;typedef unsigned long long ull;typedef long long ll;const int inf = 0x3f3f3f3f;const double eps = 1e-8;const int maxn =1e5+10;int n,m;int pa[maxn],oet[maxn];void init(){ for (int i = 0; i < maxn; i++) { pa[i] = i; } memset(oet,0,sizeof(oet));}int find(int x){ if (pa[x] == x) { return x; } else { int tmp = pa[x]; pa[x] = find(tmp); oet[x] = (oet[x]+oet[tmp])%2; return pa[x]; }}void union_set(int x,int y,int d){ int fx = find(x); int fy = find(y); if (fx == fy) return; pa[fx] = fy; oet[fx] = (oet[y]-oet[x]+d+2)%2;//oet[x] 表示x对其父亲的偏移量。至于这个式子怎么退出的，，就用向量来推，起点到终点}void query(int x,int y){ int fa = find(x); int fy = find(y); if (fa != fy) //x y不在一个集合中自然不能确定关系。 { printf("Not sure yet.\n"); return; } int tmp = (oet[x]-oet[y]+2)%2; //在求这种关系式的时候可以借助数学的向量来推导。 if (tmp==1) printf("In different gangs.\n"); else printf("In the same gang.\n");}int main(void){ int t; cin>>t; while (t--) { scanf("%d%d",&n,&m); char ch[10]; int x,y; init(); for (int i = 0; i < m; i++) { scanf("%s%d%d",ch,&x,&y); if (ch[0]=='A') { query(x,y); } else { union_set(x,y,1); } } } return 0;}
转载于:https://www.cnblogs.com/oneshot/p/3982753.html
