http://poj.org/problem?id=1703
无间道：有N名来自两个帮派的坏蛋，已知一些坏蛋两两不属于同一帮派，求判断给定两个坏蛋是否属于同一帮派。
2.4 加工并储存数据的数据结构
并查集
这题真的很简单，是食物链的弱化版，使用相似的思路来做即可——
定义并查集为：
并查集里的元素i-x表示i属于帮派x
同一个并查集的元素同时成立
可见所有元素个数为2 * N，如果i表示属于帮派A，那么i + N表示属于帮派B，每次输入两个家伙不在同一帮派的时候，就合并他们分属两个帮派的元素。我认为这是最简单最好懂的算法，那些利用复杂节点带权重接着依靠大量if-else维护并查集的做法都不够美。
有个小插曲，这题如果用cin的话会TLE，浪费我不少时间试图优化算法。我还是第一次遇到会让cin TLE的数据量。换用scanf就轻松AC
稍微扯远一点，最近看完了《数学之美》这本书，里面提到了最大熵模型，也就是“包含所有可能性”的模型。这道题目其实归根结底就是保留了所有可能性，我们只知道x和y不属于同一集合，但我们不能确定究竟x属于集合A还是集合B，于是我们保留所有可能性，对x-A和x-B都做了一次记录。
http://www.cnblogs.com/plumrain/p/POJ_1703.html
解法：并查集基础题。用一个struct node表示每一个罪犯，node.f表示该罪犯的父亲节点，node.r表示该罪犯与父亲节点对应的罪犯的关系(0表示来自同一个帮派，1表示不同)。然后写find函数注意更新node.r就行
Description
The police office in Tadu City decides to say ends to the chaos, as launch actions to root up the TWO gangs in the city, Gang Dragon and Gang Snake. However, the police first needs to identify which gang a criminal belongs to. The present question is, given two criminals; do they belong to a same clan? You must give your judgment based on incomplete information. (Since the gangsters are always acting secretly.)
Assume N (N <= 10^5) criminals are currently in Tadu City, numbered from 1 to N. And of course, at least one of them belongs to Gang Dragon, and the same for Gang Snake. You will be given M (M <= 10^5) messages in sequence, which are in the following two kinds:
1. D [a] [b]
where [a] and [b] are the numbers of two criminals, and they belong to different gangs.
2. A [a] [b]
where [a] and [b] are the numbers of two criminals. This requires you to decide whether a and b belong to a same gang.
Assume N (N <= 10^5) criminals are currently in Tadu City, numbered from 1 to N. And of course, at least one of them belongs to Gang Dragon, and the same for Gang Snake. You will be given M (M <= 10^5) messages in sequence, which are in the following two kinds:
1. D [a] [b]
where [a] and [b] are the numbers of two criminals, and they belong to different gangs.
2. A [a] [b]
where [a] and [b] are the numbers of two criminals. This requires you to decide whether a and b belong to a same gang.
Input
The first line of the input contains a single integer T (1 <= T <= 20), the number of test cases. Then T cases follow. Each test case begins with a line with two integers N and M, followed by M lines each containing one message as described above.
Output
For each message "A [a] [b]" in each case, your program should give the judgment based on the information got before. The answers might be one of "In the same gang.", "In different gangs." and "Not sure yet."
Sample Input
1 5 5 A 1 2 D 1 2 A 1 2 D 2 4 A 1 4
Sample Output
Not sure yet. In different gangs. In the same gang.
http://blog.csdn.net/freezhanacmore/article/details/8774033
题意 ：有两个不同的帮派，每个帮派至少有一个人。 判断两个人是否属于同一个帮派。有 T 组测试数据。给你 N 个人，编号从 1 到 N，操作 M 次。每次操作输入一个字符和两个数 x ,y如果字符为 A 则判断 x 和 y 是否属于同一个帮派，并且输出结果。如果字符为 D 则明确告诉你 x 和 y 是属于不同帮派的。算法：经典并查集的应用。PS：以前接触的并查集都是让我们判断是否属于同一个连通分量，但这道题却让你判断是否属于同一类。开始小纠结了下，如果我昨天没有纠结清楚 POJ 1182 食物链 那题想必肯定是做不出来的，其实想清楚了，这道题就是 食物链那题的简单版本。思路：除了像普通的并查集定义一个 p[] 记录父亲节点外，还定义一个 r[] 记录当前点与其所属的连通分量的根节点的关系。r[] = 0 表示属于同一个帮派； r[] = 1表示与其根节点属于不同的帮派。开始时初始化自己是自己的父亲 p[x] = x，自己与自己属于同一类 r[x] = 0.一旦输入 D 断定 x 和 y 属于不同集合后，就连接 x 和 y 所在的树，同时更新 r[]一旦输入 A如果 find(x) 不等于 find(y) 说明还没有判断过 x 与 y 直接输出关系不确定即可Not sure yet.如果find(x)等于 find(y) ，但是他们的r不等，说明属于不同帮派，输出In different gangs.如果他们的r相等，说明属于同一个帮派，则输出In the same gang注意：1.find()函数寻找根节点的时候要不断的更新 r根据子节点与父亲节点的关系和父节点与爷爷节点的关系，推导子节点与爷爷节点的关系如果 a 和 b 的关系是 r1, b 和 c 的关系是 r2,那么 a 和 c 的关系就是 (r1+r2)%2 . PS:因为只用两种情况所以对 2 取模。如果实在不好理解，那么我们就枚举推理一下，共有 2*2 = 4种情况：（a, b） (b, c) (a, c) (r1+r2)%20 0 0 0 a 和 b是同类 ， b 和 c 是同类， 所以 a 和 c 也是同类0 1 1 1 a 和 b是同类 ， b 和 c 是异类， 所以 a 和 c 也是异类1 0 1 1 a 和 b是异类 ， b 和 c 是同类， 所以 a 和 c 是异类1 1 0 0 a 和 b是异类 ， b 和 c 是异类， 所以 a 和 c 是同类2.Union（）联合两棵树的时候也要更新两棵树的根的关系定义：fx 为 x的根节点， fy 为 y 的根节点联合时，使得 p[fx] = fy; 同时也要寻找 fx 与 fy 的关系。关系为：（r[x]+r[y]+1）%2如何证明？fx 与 x 的关系是 r[x],x 与 y 的关系是 1 （因为确定是不同类，才联合的）,y 与 fy 关系是 r[y],模 2 是因为只有两种关系所以又上面的一点所推出的定理可以证明 fx 与 fy 的关系是： （r[x]+r[y]+1）%2
- const int maxn = 100000+10;
- int p[maxn]; //存父亲节点
- int r[maxn]; //存与根节点的关系，0 代表同类， 1代表不同类
- int find(int x) //找根节点
- {
- if(x == p[x]) return x;
- int t = p[x]; //记录父亲节点 方便下面更新r[]
- p[x] = find(p[x]);
- r[x] = (r[x]+r[t])%2; //根据子节点与父亲节点的关系和父节点与爷爷节点的关系，推导子节点与爷爷节点的关系
- return p[x]; //容易忘记
- }
- void Union(int x, int y)
- {
- int fx = find(x); //x所在集合的根节点
- int fy = find(y);
- p[fx] = fy; //合并
- r[fx] = (r[x]+1+r[y])%2; //fx与x关系 + x与y的关系 + y与fy的关系 = fx与fy的关系
- }
- void set(int n)
- {
- for(int x = 1; x <= n; x++)
- {
- p[x] = x; //自己是自己的父节点
- r[x] = 0; //自己和自己属于同一类
- }
- }
- int main()
- {
- int T;
- int n, m;
- scanf("%d", &T);
- while(T--)
- {
- scanf("%d%d%*c", &n, &m);
- set(n);
- char c;
- int x, y;
- while(m--)
- {
- scanf("%c%d%d%*c", &c, &x, &y); //注意输入
- //printf("%c\n", c);
- if(c == 'A')
- {
- if(find(x) == find(y)) //如果根节点相同，则表示能判断关系
- {
- if(r[x] != r[y]) printf("In different gangs.\n");
- else printf("In the same gang.\n");
- }
- else printf("Not sure yet.\n");
- }
- else if(c == 'D')
- {
- Union(x, y);
- }
- }
- }
- return 0;
- }
http://www.hankcs.com/program/cpp/poj-1703-find-them-catch-them.html无间道：有N名来自两个帮派的坏蛋，已知一些坏蛋两两不属于同一帮派，求判断给定两个坏蛋是否属于同一帮派。
2.4 加工并储存数据的数据结构
并查集
这题真的很简单，是食物链的弱化版，使用相似的思路来做即可——
定义并查集为：
并查集里的元素i-x表示i属于帮派x
同一个并查集的元素同时成立
可见所有元素个数为2 * N，如果i表示属于帮派A，那么i + N表示属于帮派B，每次输入两个家伙不在同一帮派的时候，就合并他们分属两个帮派的元素。我认为这是最简单最好懂的算法，那些利用复杂节点带权重接着依靠大量if-else维护并查集的做法都不够美。
有个小插曲，这题如果用cin的话会TLE，浪费我不少时间试图优化算法。我还是第一次遇到会让cin TLE的数据量。换用scanf就轻松AC
稍微扯远一点，最近看完了《数学之美》这本书，里面提到了最大熵模型，也就是“包含所有可能性”的模型。这道题目其实归根结底就是保留了所有可能性，我们只知道x和y不属于同一集合，但我们不能确定究竟x属于集合A还是集合B，于是我们保留所有可能性，对x-A和x-B都做了一次记录。
#define MAX_N 100000 * 2 + 16int parent[MAX_N];int height[MAX_N];void init(const int& n){ for (int i = 0; i < n; ++i) { parent[i] = i; height[i] = 0; }}int find(const int& x){ if (parent[x] == x) { return x; } else { return parent[x] = find(parent[x]); }}void unite(int x, int y){ x = find(x); y = find(y); if (x == y) { return; } if (height[x] < height[y]) { parent[x] = y; } else { parent[y] = x; if (height[x] == height[y]) { ++height[x]; } }}bool same(const int& x, const int& y){ return find(x) == find(y);}int main(int argc, char *argv[]){#ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout);#endif int T; cin >> T; while (T--) { int N, M; cin >> N >> M; init(N * 2); char message; int x, y; getchar(); while (M--) { // cin 会导致TLE，哭笑不得 // cin >> message >> x >> y; scanf("%c%d%d%*c", &message, &x, &y); if (message == 'A') { if (same(x, y)) { cout << "In the same gang." << endl; } else if (same(x, y + N)) { cout << "In different gangs." << endl; } else { cout << "Not sure yet." << endl; } } else { unite(x, y + N); unite(x + N, y); } } }#ifndef ONLINE_JUDGE fclose(stdin); fclose(stdout); system("out.txt");#endif return 0;}http://www.cnblogs.com/plumrain/p/POJ_1703.html
解法：并查集基础题。用一个struct node表示每一个罪犯，node.f表示该罪犯的父亲节点，node.r表示该罪犯与父亲节点对应的罪犯的关系(0表示来自同一个帮派，1表示不同)。然后写find函数注意更新node.r就行
struct node{ 14 int f, r; 15 }; 17 char s[10]; 18 int n, m; 19 node a[maxn]; 21 void init() 22 { 23 for (int i = 0; i < n; ++ i){ 24 a[i].f = i; 25 a[i].r = 0; 26 } 27 } 29 int find(int x) 30 { 31 if (x == a[x].f){ 32 a[x].r = 0; 33 return x; 34 } 36 int y = a[x].f; 37 a[x].f = find(a[x].f); 38 a[x].r = (a[y].r + a[x].r) % 2; 39 return a[x].f; 40 } 42 void merge(int x, int y) 43 { 44 int t1 = find(x), t2 = find(y); 45 a[t1].f = t2; 46 a[t1].r = (a[y].r + a[x].r + 1) % 2; 47 } 49 int main() 50 { 51 int T; 52 scanf ("%d", &T); 53 while (T --){ 54 scanf ("%d%d", &n, &m); 55 init(); 57 int x, y; 58 while (m --){ 59 scanf ("%s%d%d", s, &x, &y); 60 int t1 = find(x), t2 = find(y); 61 if (s[0] == 'D') 62 merge(x, y); 63 else{ 64 if (t1 != t2) 65 printf ("Not sure yet.\n"); 66 else{ 67 if (a[x].r == a[y].r) 68 printf ("In the same gang.\n"); 69 else 70 printf ("In different gangs.\n"); 71 } 72 } 73 } 74 } 75 return 0; 76 }Read full article from 1703 -- Find them, Catch them
