leetcode261. 以图判树

给定从 0 到 n-1 标号的 n 个结点，和一个无向边列表（每条边以结点对来表示），请编写一个函数用来判断这些边是否能够形成一个合法有效的树结构。

示例 1：

输入: n = 5, 边列表 edges = [[0,1], [0,2], [0,3], [1,4]]
输出: true
示例 2:

输入: n = 5, 边列表 edges = [[0,1], [1,2], [2,3], [1,3], [1,4]]
输出: false
注意：你可以假定边列表 edges 中不会出现重复的边。由于所有的边是无向边，边 [0,1] 和边 [1,0] 是相同的，因此不会同时出现在边列表 edges 中。

思路：并查集，没有环（find(x)!=find(y)），并且根=1（根多了就是森林了），我们认为是一颗树。

  

   

    

     

    
    

     

      class Solution {
     
    
   

    

     

    
    

     
 int[] parent;//这是记录关系的数组
     
    
   

    

     

    
    

     
 //查找
     
    
   

    

     

    
    

     
 int find(int parent[], int i) {
     
    
   

    

     

    
    

     
 if (parent[i] == -1)
     
    
   

    

     

    
    

     
 return i;
     
    
   

    

     

    
    

     
 return find(parent, parent[i]);
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 //合并
     
    
   

    

     

    
    

     
 void union(int parent[], int x, int y) {
     
    
   

    

     

    
    

     
 int xset = find(parent, x);
     
    
   

    

     

    
    

     
 int yset = find(parent, y);
     
    
   

    

     

    
    

     
 if (xset != yset)
     
    
   

    

     

    
    

     

       parent[xset] = yset;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 public boolean validTree(int n, int[][] edges) {
     
    
   

    

     

    
    

     
 int len=edges.length;
     
    
   

    

     

    
    

     

       parent = new int[n];
     
    
   

    

     

    
    

     

       Arrays.fill(parent, -1);
     
    
   

    

     

    
    

     
 for (int i = 0; i < len; i++) {
     
    
   

    

     

    
    

     
 if(find(parent,edges[i][0])==find(parent,edges[i][1]))return false;
     
    
   

    

     

    
    

     

       union(parent, edges[i][0], edges[i][1]);
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 int count = 0;
     
    
   

    

     

    
    

     
 //查根的数量
     
    
   

    

     

    
    

     
 for (int i = 0; i < n; i++)
     
    
   

    

     

    
    

     
 if (parent[i] == -1)
     
    
   

    

     

    
    

     

       count++;
     
    
   

    

     

    
    

     
 return count==1;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

      }
     
    
  
 

文章来源: fantianzuo.blog.csdn.net，作者：兔老大RabbitMQ，版权归原作者所有，如需转载，请联系作者。

原文链接：fantianzuo.blog.csdn.net/article/details/104424817