并查集是一种树型的数据结构，用于处理一些不交集的合并及查询问题。
给出一个有向图，经过并查集算法可以很快地判断任意连个点是否属于同一个集合。
#include<iostream>#include<stdio.h>#include<string.h>#define MAXN 1000using namespace std;int root[MAXN]; //the root of a nodeintlayer[MAXN];int n, m;//the number of node and edgevoid init(){for (int i = 0; i < n; i++){root[i] = i;layer[i] = 0;}}//find the finaly root and updata the journeyint find_root(int a){if (root[a] == a ) return a;return root[a] = find_root(root[a]);}//connect tow nodevoid unite(int a, int b){int aroot = find_root(a);int broot = find_root(b);if (aroot == broot) return;// node with smaller ranke connect to the another rootif (layer[aroot] < layer[broot])root[aroot] = broot;else root[broot] = aroot;//only if tow node equal to rank then change layerif (layer[aroot] == layer[broot]) layer[aroot]++;}int main(){cin >> n >> m;init();while (m--){int a, b;cin >> a >> b;unite(a, b);}//show the resultfor (int i = 0; i < n; i++){printf("%d ---> %d n", i, root[i]);//if root[i] is same then those node come from a same set}return 0;}/*example input:8 60 13 11 45 26 27 6 */