Number of Provinces

Problem statement

You get an n × n matrix isConnected for n cities. isConnected[i][j] == 1 means city i and city j are directly linked (and the matrix is symmetric). A province is a set of cities connected directly or through other cities — essentially one connected component.

Return how many provinces there are.

Example:

Input:

isConnected = [[1,1,0],[1,1,0],[0,0,1]]

Expected output:

2

Why: cities 0 and 1 form one province; city 2 is alone.

Practice on LeetCode: Number of Provinces

Golang Solution

Build an adjacency list from the matrix, then DFS from every unvisited city. Each time you start a DFS, you have discovered a new province.

Time: O(n²) — scanning the matrix dominates
Space: O(n²) worst case for the adjacency list, plus O(n) for visited / recursion

func findCircleNum(isConnected [][]int) int {
    n := len(isConnected)

    visited := make([]bool, n)
    count := 0

    // Build adjacency list
    adjList := make([][]int, n)

    for i := 0; i < n; i++ {
        for j := 0; j < n; j++ {
            if i != j && isConnected[i][j] == 1 {
                adjList[i] = append(adjList[i], j)
            }
        }
    }

    // DFS
    var dfs func(int)

    dfs = func(node int) {
        visited[node] = true

        for _, neighbor := range adjList[node] {
            if !visited[neighbor] {
                dfs(neighbor)
            }
        }
    }

    // Count connected components
    for i := 0; i < n; i++ {
        if !visited[i] {
            count++
            dfs(i)
        }
    }

    return count
}