Problem Description

There are n cities. Some of them are connected, while some are not. If city a is connected directly with city b, and city b is connected directly with city c, then city a is connected indirectly with city c.

A province is a group of directly or indirectly connected cities and no other cities outside of the group.

You are given an n x n matrix isConnected where isConnected[i][j] = 1 if the ith city and the jth city are directly connected, and isConnected[i][j] = 0 otherwise.

Return the total number of provinces.

Problem Link

Solution 1: Union-Find

This problem is a typical use case for the Union-Find (Disjoint Set Union) data structure, which is efficient for handling.

Code

type UnionFind struct {
    parent []int
    height []int
    count int
}

func NewUnionFind(n int) *UnionFind {
    uf := &UnionFind{
        parent: make([]int, n),
        height: make([]int, n),
        count: n,
    }
    for i := 0; i < n; i++ {
        uf.parent[i] = i
        uf.height[i] = 1
    }
    return uf
}

func (uf *UnionFind) Find(x int) int {
    if uf.parent[x] != x {
        uf.parent[x] = uf.Find(uf.parent[x])
    }
    return uf.parent[x]
}

func (uf *UnionFind) Merge(x, y int) {
    rootX := uf.Find(x)
    rootY := uf.Find(y)
    
    if rootX != rootY {
        if uf.height[rootX] > uf.height[rootY] {
            uf.parent[rootY] = rootX
        } else if uf.height[rootX] < uf.height[rootY] {
            uf.parent[rootX] = rootY
        } else {
            uf.parent[rootY] = rootX
            uf.height[rootX]++
        }
        uf.count--
    }
    
}

func findCircleNum(isConnected [][]int) int {
    length := len(isConnected)
    uf := NewUnionFind(length)
    for i := 0; i < length; i++ {
        for j := i+1; j < length; j++ {
            if isConnected[i][j] == 1 {
                uf.Merge(i, j)
            }
        }
    }
    return uf.count
}

Time Complexity: O(n^2)

Space Complexity: O(n)

Note: just like leetcode-200, we can also use DFS or BFS to solve this problem.