😲323 Number of Connected Components in an Undirected Graph (using union find~)

https://leetcode.com/problems/number-of-connected-components-in-an-undirected-graph/

用bfs当然是可以做的

class Solution {
    public int countComponents(int n, int[][] edges) {
        Map<Integer, List<Integer>> map = buildGraph(edges);
        Set<Integer> visited = new HashSet<>();
        int cnt = 0;
        for (int i = 0; i < n; i++) {
            if (!visited.contains(i)) {
                bfs(i, visited, map);
                cnt++;
            }
        }
        return cnt;
    }
    private void bfs(int idx, Set<Integer> visited, Map<Integer, List<Integer>> map) {
        Queue<Integer> queue = new ArrayDeque<>();
        queue.offer(idx);
        while (!queue.isEmpty()) {
            int node = queue.poll();
            if (visited.contains(node)) {
                continue;
            }
            visited.add(node);
            
            List<Integer> neighbors = map.get(node);
            if (neighbors == null) {
                continue;
            }
            for (int nei : neighbors) {
                queue.offer(nei);
            }
        }
    }
    private Map<Integer, List<Integer>> buildGraph(int[][] edges) {
        Map<Integer, List<Integer>> map = new HashMap<>();
        for (int[] edge : edges) {
            List<Integer> listA = map.get(edge[0]);
            if (listA == null) {
                listA = new ArrayList<>();
            }
            listA.add(edge[1]);
            map.put(edge[0], listA);
            
            List<Integer> listB = map.get(edge[1]);
            if (listB == null) {
                listB = new ArrayList<>();
            }
            listB.add(edge[0]);
            map.put(edge[1], listB);
        }
        return map;
    }
}

但是这道题可以用union find 感觉可以学习下

public class Solution {

    private int find(int[] representative, int vertex) {
        if (vertex == representative[vertex]) {
            return vertex;
        }
        
        return representative[vertex] = find(representative, representative[vertex]);
    }
    
    private int combine(int[] representative, int[] size, int vertex1, int vertex2) {
        vertex1 = find(representative, vertex1);
        vertex2 = find(representative, vertex2);
        
        if (vertex1 == vertex2) {
            return 0;
        } else {
            if (size[vertex1] > size[vertex2]) {
                size[vertex1] += size[vertex2];
                representative[vertex2] = vertex1;
            } else {
                size[vertex2] += size[vertex1];
                representative[vertex1] = vertex2;
            }
            return 1;
        }
    }

    public int countComponents(int n, int[][] edges) {
        int[] representative = new int[n];
        int[] size = new int[n];
        
        for (int i = 0; i < n; i++) {
            representative[i] = i;
            size[i] = 1;
        }
        
        int components = n;
        for (int i = 0; i < edges.length; i++) { 
            components -= combine(representative, size, edges[i][0], edges[i][1]);
        }

        return components;
    }
}