323. Number of Connected Components in an Undirected Graph

JIAKAOBO

LeetCode

感谢赞助!

• ㊗️
• 大家
• offer
• 多多！

Problem

Given n nodes labeled from 0 to n - 1 and a list of undirected edges (each edge is a pair of nodes), write a function to find the number of connected components in an undirected graph.

Example 1:

Input: n = 5 and edges = [[0, 1], [1, 2], [3, 4]]

     0          3
     |          |
     1 --- 2    4

Output: 2

Example 2:

Input: n = 5 and edges = [[0, 1], [1, 2], [2, 3], [3, 4]]

     0           4
     |           |
     1 --- 2 --- 3

Output:  1

Note: You can assume that no duplicate edges will appear in edges. Since all edges are undirected, [0, 1] is the same as [1, 0] and thus will not appear together in edges.

Code

DFS

class Solution {
    public int countComponents(int n, int[][] edges) {
        boolean[] visited = new boolean[n];
        int count = 0;

        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                helper(edges, visited, i);
                count++;
            }
        }
        return count;
    }

    private void helper(int[][] edges, boolean[] visited, int node) {
        if (visited[node]) return;
        visited[node] = true;
        for (int[] edge : edges) {
            int x = edge[0];
            int y = edge[1];
            if (x == node && !visited[y]) {
                helper(edges, visited, y);
            }

            if (y == node && !visited[x]) {
                helper(edges, visited, x);
            }
        }
    }
}

BFS

class Solution {
    public int countComponents(int n, int[][] edges) {
        boolean[] visited = new boolean[n];
        Queue<Integer> queue = new LinkedList<>();

        int count = 0;

        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                queue.offer(i);
                while (!queue.isEmpty()) {
                    int curr = queue.poll();
                    visited[curr] = true;
                    for (int[] edge : edges) {
                        int x = edge[0];
                        int y = edge[1];
                        if (x == curr && !visited[y]) {
                            queue.offer(y);
                        }

                        if (y == curr && !visited[x]) {
                            queue.offer(x);
                        }
                    }
                }
                count++;
            }
        }
        return count;
    }
}

union find

class Solution {
    public class UnionFind {
        int[] parents;
        int[] ranks;
        int groupNum = 0;

        // one dimension
        public UnionFind(int n) {
            parents = new int[n];
            ranks = new int[n];

            for (int i = 0; i < n; i++) {
                parents[i] = i;
                ranks[i] = 1;
            }

            groupNum = n;
        }

        public boolean union(int x, int y) {
            int xParent = find(x);
            int yParent = find(y);
            // same parent
            if (xParent == yParent) return false;
            // different parent
            groupNum--;
            if (ranks[xParent] > ranks[yParent]) {
                parents[yParent] = xParent;
            } else if (ranks[xParent] < ranks[yParent]) {
                parents[xParent] = yParent;
            } else {
                parents[yParent] = xParent;
                ranks[xParent]++;
            }

            return true;
        }

        public int find(int node) {
            while (node != parents[node]) {
                int parentNode = parents[parents[node]];

                parents[node] = parentNode;
                node = parentNode;
            }

            return node;
        }

        public int getGroupNum() {
            return groupNum;
        }
    }

    public int countComponents(int n, int[][] edges) {
        UnionFind node = new UnionFind(n);

        for(int[] edge : edges){
            node.union(edge[0], edge[1]);
        }

        return node.getGroupNum();
    }
}