178. 그림 이 나무 인지 아 닌 지

묘사 하 다.
n 개의 노드 를 제시 하고 레이 블 은 각각 0 에서 n - 1 까지 이 무 방향 그림 이 나무 인지 아 닌 지 를 판단 하 는 함 수 를 작성 합 니 다.
주의 사항
당신 은 우리 가 반복 되 는 변 이 변 의 목록 에 있다 고 가정 할 수 있 습 니 다. 무 방향 변 [0, 1] 과 [1, 0] 은 같은 변 이기 때문에 그들 은 우리 가 당신 에 게 준 변 의 목록 에 동시에 나타 나 지 않 을 것 입 니 다.
알고리즘 제4 판 정의
V 개의 결점 을 포함 하 는 그림 G 가 아래 의 5 가지 조건 을 만족 시 킬 때 그것 은 바로 나무 이다. 1. G 는 V - 1 개의 변 이 있 고 고리 가 없 으 며 2. G 는 V - 1 개의 변 이 있 으 며 연 결 된 3. G 는 연통 그림 이 고 임의의 변 을 삭제 하면 연결 되 지 않 는 다. 4. G 는 고리 가 없 지만 임의의 변 을 추가 하면 고리 가 생 긴 다. 5. G 중 임의의 한 쌍 의 정점 사이 에 간단 한 경로 만 존재 한다.(정점 시퀀스 에서 정점 이 반복 되 지 않 는 경로)
본보기
n = 5 를 주 고 edges = [0, 1], [0, 2], [0, 3], [1, 4] 를 주 고 true 를 되 돌려 줍 니 다. n = 5 를 주 고 edges = [0, 1], [1, 2], [2, 3], [1, 3], [1, 4] 를 주 고 false 를 되 돌려 줍 니 다.
판단 조건

n 개의 점 이 n - 1 개의 변 이 존재 하지 않 으 면 반드시 링

이 존재 합 니 다.

한 점 에서 다른 모든 점 을 방문 할 수 있 고 점 의 총 수 는 n

이다.
코드

BFS 판단 연통 성

public class Solution {
    /**
     * @param n an integer
     * @param edges a list of undirected edges
     * @return true if it's a valid tree, or false
     */
    public boolean validTree(int n, int[][] edges) {
        if (n == 0) {
            return false;
        }
        //                  
        if (edges.length != n - 1) {
            return false;
        }

        // set     ，          
        Map> graph = initializeGraph(n, edges);  
          
        // bfs
        // queue          
        Queue queue = new LinkedList<>();      
        Set hash = new HashSet<>();
        
        queue.offer(0);
        hash.add(0);     // hashset    offer   
        // queue    while            
        while (!queue.isEmpty()) {        
            int node = queue.poll();
            // foreach   ，neighbor     
            // graph.get(node)         
            for (Integer neighbor : graph.get(node)) {          
                // hash          ，              
                //          ，      ，A   B      ，B   A      ，         
                if (hash.contains(neighbor)) {                
                    continue;
                }
                hash.add(neighbor);
                queue.offer(neighbor);
            }
        }

        //     n-1      n            
        return (hash.size() == n);                 
    }
    
    //               
    private Map> initializeGraph(int n, int[][] edges) {
       // set               ，set                
       //                     ，         ，      
        Map> graph = new HashMap<>();
        for (int i = 0; i < n; i++) {
            // hashset            ,
            // hashmap    put              ，
            //          n    
            graph.put(i, new HashSet());   
        }
        
        //        n，n      
        // i       ，     n，    n    i = n - 1       ，    
        for (int i = 0; i < edges.length; i++) {               
            int u = edges[i][0];
            int v = edges[i][1];
            graph.get(u).add(v);
            graph.get(v).add(u);
        }
          //                                                 
          // get()          ,  graph    hashset   ,
          // graph.get(v).add(u)    hashset.add()
          // u   v           graph.get(u)   u,v        i，
          // u.add(v)       u   v   (graph      u   set   
          //      v    )，                   

        return graph;
    }
}

Union Find

public class Solution {
      class UnionFind{
        HashMap father = new HashMap();
        UnionFind(int n){
            for(int i = 0 ; i < n; i++) {
                father.put(i, i); 
            }
        }
        int compressed_find(int x){
            int parent =  father.get(x);
            while(parent!=father.get(parent)) {
                parent = father.get(parent);
            }
            int temp = -1;
            int fa = father.get(x);
            while(fa!=father.get(fa)) {
                temp = father.get(fa);
                father.put(fa, parent) ;
                fa = temp;
            }
            return parent;
                
        }
        
        void union(int x, int y){
            int fa_x = compressed_find(x);
            int fa_y = compressed_find(y);
            if(fa_x != fa_y)
                father.put(fa_x, fa_y);
        }
    }
    /**
     * @param n an integer
     * @param edges a list of undirected edges
     * @return true if it's a valid tree, or false
     */
    public boolean validTree(int n, int[][] edges) {
        // tree should have n nodes with n-1 edges
        if (n - 1 != edges.length) {
            return false;
        }
        
        UnionFind uf = new UnionFind(n);
        
        for (int i = 0; i < edges.length; i++) {
            if (uf.compressed_find(edges[i][0]) == uf.compressed_find(edges[i][1])) {
                return false;
            }
            uf.union(edges[i][0], edges[i][1]);
        }
        return true;
    }
}