Number of Connected Components in an Undirected Graph

Similar Problems:

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.

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

- Solution:

// Blog link: https://code.dennyzhang.com/number-of-connected-components-in-an-undirected-graph // Basic Ideas: union find // // Complexity: Time O(m), Space O(n) type UF struct { parent []int } func constructor(size int) UF{ parent := make([]int, size) for i, _ := range parent { parent[i] = i } return UF{parent:parent} } func (uf *UF) union(x, y int){ // TODO: rank based merge uf.parent[uf.find(y)] = uf.find(x) } func (uf *UF) find(x int) int { // TODO: path compression for uf.parent[x] != x { x = uf.parent[x] } return x } func countComponents(n int, edges [][]int) int { uf := constructor(n) for _, edge := range edges { uf.union(edge[0], edge[1]) } m := map[int]bool{} for i:=0; i<n; i++ { m[uf.find(i)] = true } return len(m) }