Welcome to Subscribe On Youtube

Question

Formatted question description: https://leetcode.ca/all/323.html

Level

Medium

Description

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.

Algorithm

DFS

One solution is to use DFS. The idea is to give each node a flag to mark whether it has been visited. For an unvisited node, we will increment the result by 1, because this must be a new connected region. , And then we traverse the neighboring nodes through the adjacency list and mark them as visited.

After traversing all connected nodes, we continue to look for the next unvisited node, and so on until all nodes have been visited, then the number of connected regions is also calculated at this time

Union Find

Create a root array with the same subscript and node value. At this time, root[i] indicates that node i belongs to group i. We initialized n parts (res = n), assuming that each node belongs to a separate interval at the beginning .

Then we start to traverse all the edges. For two points of an edge, their values in the root at the beginning are not the same. At this time, we reduce the result by 1, which means one interval is missing. Then update the root of one of the nodes Value to make the root value of the two nodes the same.

Then we can mark the root values of all nodes in the connected interval as the same value, and the root values of different connected intervals are different, so that we can also find the number of connected intervals.

Code

  • import java.util.ArrayList;
import java.util.List;

public class Number_of_Connected_Components_in_an_Undirected_Graph {

    public static void main(String[] args) {
        Number_of_Connected_Components_in_an_Undirected_Graph out = new Number_of_Connected_Components_in_an_Undirected_Graph();
        Solution s = out.new Solution();

        System.out.println(s.countComponents(5, new int[][]{ {0, 1}, {1, 2}, {3, 4} }));
    }


    class Solution_dfs {

        public int countComponents(int n, int[][] edges) {
            int res = 0;
            List<List<Integer>> adj = new ArrayList<>(n);
            boolean[] isVisited = new boolean[n];
            for (int[] a : edges) {
                adj.get(a[0]).add(a[1]);
                adj.get(a[1]).add(a[0]);
            }

            for (int i = 0; i < n; ++i) {
                if (!isVisited[i]) {
                    ++res;
                    dfs(adj, isVisited, i);
                }
            }
            return res;
        }

        void dfs(List<List<Integer>> adj, boolean[] isVisited, int i) {
            if (isVisited[i]) {
                return;
            }

            isVisited[i] = true;
            for (int j = 0; j < adj.get(i).size(); ++j) {
                dfs(adj, isVisited, adj.get(i).get(j));
            }
        }
    };


    // Union-Find
    public class Solution {

        int[] map; // node => its parent

        public int countComponents(int n, int[][] edges) {
            int count = n;

            // array to store parent
            buildMap(n, edges);

            for(int[] edge : edges) {
                int parent1 = findParent(edge[0]);
                int parent2 = findParent(edge[1]);
                if(parent1 != parent2) {
                    union(parent1, parent2); // @note
                    count--;
                }
            }
            return count;
        }

        private void buildMap(int n, int[][] edges) {
            map = new int[n];
            for(int[] edge : edges) {
                map[edge[0]] = edge[0];
                map[edge[1]] = edge[1];
            }
        }

        private int findParent(int child) {
            while(map[child] != child) {// @note: if not equal, meaning its child, not itself
                child = map[child];
            }
            return child;
        }

        private void union(int child, int parent) {
            map[child] = parent;
        }
    }

}

############

class Solution {
    private int[] p;

    public int countComponents(int n, int[][] edges) {
        p = new int[n];
        for (int i = 0; i < n; ++i) {
            p[i] = i;
        }
        for (int[] e : edges) {
            int a = e[0], b = e[1];
            p[find(a)] = find(b);
        }
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            if (i == find(i)) {
                ++ans;
            }
        }
        return ans;
    }

    private int find(int x) {
        if (p[x] != x) {
            p[x] = find(p[x]);
        }
        return p[x];
    }
}

  • // OJ: https://leetcode.com/problems/number-of-connected-components-in-an-undirected-graph/
// Time: O(E + N)
// Space: O(N)
class UnionFind {
    vector<int> id;
    int cnt;
public:
    UnionFind(int n) : cnt(n), id(n) {
        iota(begin(id), end(id), 0);
    }
    int find(int a) {
        return id[a] == a ? a : (id[a] = find(id[a]));
    }
    void connect(int a, int b) {
        int p = find(a), q = find(b);
        if (p == q) return;
        id[p] = q;
        --cnt;
    }
    int getCount() {
        return cnt;
    }
};
class Solution {
public:
    int countComponents(int n, vector<vector<int>>& E) {
        UnionFind uf(n);
        for (auto &e : E) {
            uf.connect(e[0], e[1]);
        }
        return uf.getCount();
    }
};

  • class Solution:
    def countComponents(self, n: int, edges: List[List[int]]) -> int:
        def find(x):
            if p[x] != x:
                p[x] = find(p[x])
            return p[x]

        p = list(range(n))
        for a, b in edges:
            p[find(a)] = find(b)
        return sum(i == find(i) for i in range(n)) # or len(set(parents))

############

class Solution: # more literal
    def countComponents(self, n: int, edges: List[List[int]]) -> int:
        # Initialize parent array for union-find
        parent = [i for i in range(n)]
        
        # Perform union-find on each edge
        for u, v in edges:
            self.union(u, v, parent)
        
        # Count the number of distinct parents (connected components)
        count = len(set(self.find(x, parent) for x in range(n)))
        return count
    
    def union(self, x: int, y: int, parent: List[int]) -> None:
        rootX = self.find(x, parent)
        rootY = self.find(y, parent)
        if rootX != rootY:
            parent[rootX] = rootY
    
    def find(self, x: int, parent: List[int]) -> int:
        if parent[x] != x:
            parent[x] = self.find(parent[x], parent)
        return parent[x]

  • func countComponents(n int, edges [][]int) (ans int) {
	p := make([]int, n)
	for i := range p {
		p[i] = i
	}
	var find func(int) int
	find = func(x int) int {
		if p[x] != x {
			p[x] = find(p[x])
		}
		return p[x]
	}
	for _, e := range edges {
		a, b := e[0], e[1]
		p[find(a)] = find(b)
	}
	for i := 0; i < n; i++ {
		if i == find(i) {
			ans++
		}
	}
	return
}

  • /**
 * @param {number} n
 * @param {number[][]} edges
 * @return {number}
 */
var countComponents = function (n, edges) {
    let p = new Array(n);
    for (let i = 0; i < n; ++i) {
        p[i] = i;
    }
    function find(x) {
        if (p[x] != x) {
            p[x] = find(p[x]);
        }
        return p[x];
    }
    for (const [a, b] of edges) {
        p[find(a)] = find(b);
    }
    let ans = 0;
    for (let i = 0; i < n; ++i) {
        if (i == find(i)) {
            ++ans;
        }
    }
    return ans;
};

All Problems

All Solutions