并查集 (261. Graph Valid Tree)
- Graph Valid Tree 的另一种做法。
判断 graph 是不是 tree
1.树中没有形成环 (nodes don’t have circle)
2.连通分量的个数为 1 (only 1 root node)
并查集代码如下:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42
| public boolean validTree(int n, int[][] edges) { //数组p用来存储每个节点的祖宗 int[] p = new int[n]; //初始化,每个节点的祖宗初始化为它自己 for(int i =0; i < n; i++){ p[i] = i; } //集合的合并操作 for(int j = 0; j < edges.length;j++){ //遍历的过程,如果发现有环,则直接退出 if(find(edges[j][0],p) == find(edges[j][1],p)){ return false; }else{ //否则合并两个集合 union(edges[j][0],edges[j][1],p); } } //用来存储连通分量的个数 int c = 0; for(int i = 0; i < n; i++){ //根节点(连通分量)的个数 if(p[i] == i){ c++; } } //判断是否只有一个根节点 return c == 1; }
//两个集合的合并操作 void union(int x,int y,int[] p){ //如果两个节点的祖宗不相等,则将两个集合合并 int fx = find(x,p), fy = find(y,p); if(fx != fy) p[fx] = fy; }
//查找一个节点的祖宗节点 int find(int x,int[] p){ //如果当前节点的祖宗为它自己本身,则为根节点,否则继续往上递归 if(p[x] != x) p[x] = find(p[x],p); return p[x]; }
|