# 0323. Number of Connected Components in an Undirected Graph
###### tags: `Leetcode` `Medium` `Bloomberg` `DFS` `Union Find`
Link: https://leetcode.com/problems/number-of-connected-components-in-an-undirected-graph/
## 思路
### Union Find O(E*C) O(V)
初始定义components = n（假设每个点都是独立的）
对于每一条边 做并查集的操作
如果两个端点的father是一样的，那么说明这两个点之前已经合并起来了，components数目不变
如果两个端点的father不一样，则需要合并这两个点，components数量-1

在这里官方解答用了 按rank合并的优化 也就是根据深度 对于两个父节点a,b a的child如果比b的少，那么a当b的father， vice versa

时间复杂度分析：由于对边做并查集 所以O(E) 每次并查集的操作时间复杂度可以用一个常数表示
空间复杂度分析：开了一个size n的array存father和以该点为father的集合的size
### DFS O(E+V) O(E+V)
先把邻居互相存起来，然后做dfs，做dfs的次数就是答案
时间复杂度分析：把邻居存起来 O(E) dfs要把每个点都访问一遍O(V)
空间复杂度分析：把邻居存起来 O(E) stack O(V)

## Code
### Union Find

class Solution {
    private int[] fa;
    private int[] size;
    public int countComponents(int n, int[][] edges) {
        fa = new int[n];
        size = new int[n];
        for(int i = 0;i < n;i++){
            fa[i] = i;
            size[i] = 1;
        }
    
        int components = n;
        for(int i = 0;i < edges.length;i++){
            components -= combine(edges[i][0], edges[i][1]);
        }
        return components;
    }
    public int combine(int a, int b){
        a = find(a);
        b = find(b);
        if(a==b) return 0;
        else{
            if(size[a]<size[b]){
                size[b] += size[a];
                fa[a] = b;
            }
            else{
                size[a] += size[b];
                fa[b] = a;
            }
            return 1;
        }
    }
    public int find(int a){
        if(fa[a] == a){
            return a;
        }
        return fa[a] = find(fa[a]);
    }
}

### DFS

class Solution {
    public int countComponents(int n, int[][] edges) {
        int ans = 0;
        boolean[] visited = new boolean[n];
        
        List<Integer>[] adjList = new ArrayList[n];
        for(int i = 0;i < n;i++){
            adjList[i] = new ArrayList<>();
        }
        for(int i = 0;i < edges.length;i++){
            adjList[edges[i][0]].add(edges[i][1]);
            adjList[edges[i][1]].add(edges[i][0]);
        }
        
        for(int i = 0;i < n;i++){
            if(!visited[i]){
                dfs(i, adjList, visited);
                ans++;
            }
        }
        return ans;
    }
    public void dfs(int start, List<Integer>[] adjList, boolean[] visited){
        Stack<Integer> stack = new Stack();
        stack.push(start);
        while(!stack.isEmpty()){
            int root = stack.pop();
            visited[root] = true;
            for(int next:adjList[root]){
                if(!visited[next]){
                    stack.push(next);
                }
            }
        }
    }
}