Leetcode: Number of Connected Components in an Undirected Graph

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:

     0          3
     |          |
     1 --- 2    4

Given n = 5 and edges = [[0, 1], [1, 2], [3, 4]], return 2.

Example 2:

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

Given n = 5 and edges = [[0, 1], [1, 2], [2, 3], [3, 4]], return 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.

DFS Solution:

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52

public class Solution {     public int countComponents(int n, int[][] edges) {         if (n <= 0 || edges == null) {             return 0;         }                   if (n == 1 && edges.length == 0) {             return 1;         }                   int result = 0;         boolean[] visited = new boolean[n];                   // step 1: create the adj list from edge list         List[] adjList = new List[n];         for (int i = 0; i < n; i++) {             adjList[i] = new ArrayList<>();         }                   for (int[] edge : edges) {             int from = edge[0];             int to = edge[1];                           adjList[from].add(to);             adjList[to].add(from);         }                   // step 2: calculate the number of cc         for (int i = 0; i < n; i++) {             if (!visited[i]) {                 result++;                 countCCHelper(i, adjList, visited);             }         }                   return result;     }           private void countCCHelper(int node, List[] adjList, boolean[] visited) {         if (visited[node]) {             return;         }                   visited[node] = true;                   List<Integer> neighbors = adjList[node];                   for (int neighbor : neighbors) {             countCCHelper(neighbor, adjList, visited);         }     } }

A BFS Solution:

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62

public class Solution {     public int countComponents(int n, int[][] edges) {         if (n <= 0 || edges == null) {             return 0;         }                   if (n == 1 && edges.length == 0) {             return 1;         }                   int result = 0;         boolean[] visited = new boolean[n];                   // step 1: create the adj list from edge list         List[] adjList = new List[n];         for (int i = 0; i < n; i++) {             adjList[i] = new ArrayList<>();         }                   for (int[] edge : edges) {             int from = edge[0];             int to = edge[1];                           adjList[from].add(to);             adjList[to].add(from);         }                   // step 2: calculate the number of cc         Queue<Integer> queue = new LinkedList<>();         for (int i = 0; i < n; i++) {             if (!visited[i]) {                 result++;                 countCCHelper(i, adjList, visited, queue);             }         }                   return result;     }           private void countCCHelper(int node, List[] adjList, boolean[] visited, Queue<Integer> queue) {         fill(node, adjList, visited, queue);                   while (!queue.isEmpty()) {             int currNode = queue.poll();             List<Integer> neighbors = adjList[currNode];                           for (Integer neighbor : neighbors) {                 fill(neighbor, adjList, visited, queue);             }         }     }           private void fill(int node, List[] adjList, boolean[] visited, Queue<Integer> queue) {         if (visited[node]) {             return;         }                   visited[node] = true;                   queue.offer(node);     } }

Union-find solution:

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29

private int[] father; public int countComponents(int n, int[][] edges) {       Set<Integer> set = new HashSet<Integer>();     father = new int[n];     for (int i = 0; i < n; i++) {         father[i] = i;     }     for (int i = 0; i < edges.length; i++) {          union(edges[i][0], edges[i][1]);     }       for (int i = 0; i < n; i++){         set.add(find(i));     }     return set.size(); }   int find(int node) {     if (father[node] == node) {         return node;     }     father[node] = find(father[node]);     return father[node]; }   void union(int node1, int node2) {     father[find(node1)] = find(node2); }