323.Number of Connected Components in an Undirected Graph

1-UnionFind + Path Compression

class Solution {
    public int countComponents(int n, int[][] edges) {
        int ans = n;
        int[] root = new int[n];
        Arrays.fill(root, -1);
        for(int i = 0; i < edges.length; i++){
            int root0 = find(root, edges[i][0]);
            int root1 = find(root, edges[i][1]);
            if(root0 != root1){
                root[root0] = root1;
                ans--;
            }
        }
        return ans;
    }
    public int find(int[] root, int node){
        if(root[node] < 0)
            return node;
        else{
            //Path Compression
            root[node] = find(root, root[node]);
            return root[node];
        }
    }
}

2-DFS

class Solution {
    public int countComponents(int n, int[][] edges) {
        List<List<Integer>> adjList = new ArrayList<List<Integer>>();
        for(int i = 0; i < n; i++){
            adjList.add(new ArrayList<Integer>());
        }

        for(int[] edge : edges){
            adjList.get(edge[0]).add(edge[1]);
            adjList.get(edge[1]).add(edge[0]);
        }

        boolean[] visited = new boolean[n];
        int cnt = 0;
        for(int i = 0 ; i < n; i++){
            if(!visited[i]){
                cnt++;
                dfs(visited, i, adjList);
            }
        }
        return cnt;
    }
    public void dfs(boolean[] visited, int index, List<List<Integer>> adjList){
        visited[index] = true;
        for(int i : adjList.get(index)){
            if(!visited[i]){
                dfs(visited, i, adjList);
            }
        }
    }
}