今天，刚学习了并查集对于并查集，也有了一定的理解了。
杭电1272这一题，主要是给你几对数，表示这两个数（可以理解为村落）直接有路，而从每一个村落到另外一个村落只能有一条路，也就是不能存在环。而并查集就是将有一定联系的村落组成一个部落（也就是集合），如果给的两个村落都存在于同一个部落，也就是存在环了。
还有一种情况就是存在两个部落，也就是有些村落到不了另一些村落。这一点，我们需要通过判断 顶点数减掉边数 是否等于，如果是，那就符合，不是，那就不符合。
也就是下面的情况：
这一题还有一个很坑的地方，输入的是0 0 ，也是符合的。
下面是AC的代码：
# include <iostream>using namespace std;const int Max = 100005;int pre[Max];bool tag[Max];//判断有几个顶点的数组int finds(int x)//finds函数，找到x的根节点。{int r = x;while(r != pre[r])r = pre[r];int i = x, j;while(i != r)//压缩路径，使集合中只有一个"老大",其他的都是“小弟”，，这样查找的可以一步找到{j = pre[i];pre[i] = r;i = j;}return r;//返回根节点}int main(){int m, n, i;while(cin >> m >> n){for(i = 0; i < Max; i++){pre[i] = i;//初始化数组tag[i] = false;//初始化顶点数组}if(m == -1 && n == -1) //退出break;if(m == 0 && n == 0)//特殊情况{cout << "Yes" << endl;continue;}tag[m] = true; tag[n] = true;//标记出现的顶点int a, b, pa, pb;int flag = 0, count = 1;//flag为是否出现环，count是数边的个数while(cin >> a >> b){if(a == 0 && b == 0)break;count++;tag[a] = true; tag[b] = true; //标记顶点pa = finds(a);//查找父节点pb = finds(b);if(pa != pb)//不相同，合并pre[pa] = pb;else//相同，存在环{flag = 1;}}if(flag)//存在环{cout << "No" << endl;continue;}int t = 0;//数顶点for(i = 0; i < Max; i++){if(tag[i])t++;}if(t – count == 1)//判断是否存在两个集合。cout << "Yes" << endl;elsecout << "No" << endl;}return 0;}
对于并查集不是很理解的，推荐去看看这一篇博客：
下面的图，或许可以更好的理解。
有希望在的地方，痛苦也成欢乐
