547. Number of Provinces

At a Glance

Topic: graphs
Pattern: Union-Find or DFS on adjacency matrix
Difficulty: Medium
Companies: Amazon, Google, Microsoft, Meta, Bloomberg
Frequency: High
LeetCode: 547

Problem (one-liner)

isConnected is n x n adjacency matrix for undirected friend graph (1 edge). Return number of connected components (provinces).

Recognition Cues

Matrix adjacency for undirected graph
Same as component counting with dense storage

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

Loading diagram…

Approaches

Scan rows DFS — visit row row, flood through 1s — O(n^2).
Union-Find over edges implied by matrix — also O(n^2).

Optimal Solution

Go

func findCircleNum(isConnected [][]int) int {
	nodeCount := len(isConnected)
	visited := make([]bool, nodeCount)
	components := 0

	var dfs func(start int)
	dfs = func(start int) {
		visited[start] = true
		for neighbor := 0; neighbor < nodeCount; neighbor++ {
			if isConnected[start][neighbor] == 1 && !visited[neighbor] {
				dfs(neighbor)
			}
		}
	}

	for node := 0; node < nodeCount; node++ {
		if !visited[node] {
			components++
			dfs(node)
		}
	}
	return components
}

JavaScript

function findCircleNum(isConnected) {
  const nodeCount = isConnected.length;
  const visited = new Array(nodeCount).fill(false);
  let components = 0;

  function dfs(start) {
    visited[start] = true;
    for (let neighbor = 0; neighbor < nodeCount; neighbor += 1) {
      if (isConnected[start][neighbor] === 1 && !visited[neighbor]) {
        dfs(neighbor);
      }
    }
  }

  for (let node = 0; node < nodeCount; node += 1) {
    if (!visited[node]) {
      components += 1;
      dfs(node);
    }
  }
  return components;
}