廊坊做网站公司,深圳品牌网站推广公司,国内优秀网站网址,企腾网络推广效果怎么样题目链接#xff1a;http://poj.org/problem?id1703 题目大意#xff1a;警察抓获N个罪犯#xff0c;这些罪犯只可能属于两个团伙中的一个#xff0c;现在给出M个条件#xff08;D a b表示a和b不在同一团伙#xff09;#xff0c;对于每一个询问(A a b)确定a#xff0… 题目链接http://poj.org/problem?id1703 题目大意警察抓获N个罪犯这些罪犯只可能属于两个团伙中的一个现在给出M个条件D a b表示a和b不在同一团伙对于每一个询问(A a b)确定ab是不是属于同一团伙或者不能确定。 思路一般的并查集题目都是给出ab属于同一集合但是这题不同给出的a,b不在同一集合如果用其他方法可能太复杂在此介绍一种此类问题的通法 定义数组pre[x]表示x的父节点r[x]表示x与当前所在集合的代表元的关系0表示x与代表元属于同一团伙1表示不在同一团伙初始值都为0因为自己肯定和自己在同一团伙。 合并两个元素ab的时候 void Union(int x,int y) { int xxfind(x); // 1 int yyfind(y); // 2 pre[xx]yy; // 3 r[xx](r[y]r[x])^1; // 4 } 对于1,2,3句话不用解释与一般的并查集合并操作一样没用启发式合并而对于第4句话既然把代表元为xx的集合合并到了代表元为yy的集合那么xx与他现在的集合的代表元也就是yy的关系r[xx]肯定是要改变的至于怎么改变可以枚举所有情况然后找出规律听说可以用向量方法想但是现在不懂。同样的原来以xx为代表元的集合中的所有元素的r[]值都可能发生改变那么在此是不是要把所有的元素的r都改变一次呢答案是否定的我们可以再find操作里面改变。 查找操作 int find(int x) { if(x!pre[x]) { int fpre[x]; // 1 pre[x]find(pre[x]); r[x](r[x]r[f])%2; // 2 } return pre[x]; } 第1句话先把原来x的父节点保存起来然后路径压缩的时候就已经把r[pre[x]]修改了然后接下来就是修改r[x]r[x]的值与r[f]的值的关系很好推就是r[x](r[x]r[f])%2。 #includestdio.h
int f[100005];
int r[100005];
void set(int n)
{int i;for(i1;in;i){f[i]i;r[i]0;}
}
int find(int x)
{int t;if(x!f[x]){tf[x];f[x]find(f[x]);r[x](r[x]r[t])%2;}return f[x];
}
void Union(int x,int y)
{int xx,yy;xxfind(x);yyfind(y);f[xx]yy;r[xx](r[x]r[y])^1;
}
int main()
{int a,b,t,n,m,aa,bb;char s[3];scanf(%d,t);while(t--){scanf(%d%d,n,m);set(n);while(m--){scanf(%s%d%d,s,a,b);if(s[0]A){aafind(a);bbfind(b);if(aabbr[a]!r[b])printf(In different gangs.\n);else if(aabbr[a]r[b])printf(In the same gang.\n);elseprintf(Not sure yet.\n);}else Union(a,b);}}return 0;
} 转载于:https://www.cnblogs.com/yyf573462811/archive/2012/07/19/6365411.html
