DSA sheet · Graphs · Connected components pattern

Number of Provinces

This is the first real graph question in the sheet, and it teaches the single most useful graph idea: counting connected components. The teacher shows that the input is already a ready-made adjacency matrix, that one DFS call colours a whole group as "visited", and that the number of times we have to start a fresh DFS is the answer. She codes it with DFS and explains what changes for BFS. The same loop ("for every node, if not visited, start a traversal and count it") comes back in Number of Islands, Flood Fill, Surrounded Regions and many more.

Every part below follows the same order:
① the question in simple words → ② what the constraints tell us → ③ intuition → ④ building the logic from examples → ⑤ approach steps → ⑥ code → ⑦ code line by line → ⑧ dry run → ⑨ complexity & remember

• Part 0 · Graph basics this page needs
• Part A · Count provinces with DFS (the teacher's code)
• Part B · Count provinces with BFS
• Part C · Revision page

Part 0 · Graph basics this page needs

Nodes and edges

A graph is a set of points joined by lines. The points are called nodes (or vertices). The lines are called edges. In this problem every city is a node and every direct road between two cities is an edge.

(1)—(2)—(3)        (4)—(5)
 nodes: 1 2 3 4 5     edges: 1-2, 2-3, 4-5

Directed, undirected, weighted

Three ways the input can arrive

Most graph problems hand you an edge list, and the first job is to build an adjacency list, because it gives the neighbours of a node directly. Here is how in Python:

n = 5
edges = [[0, 1], [1, 2], [3, 4]]

adj = [[] for _ in range(n)]     # one empty list per node
for u, v in edges:
    adj[u].append(v)             # u can reach v
    adj[v].append(u)             # undirected: v can reach u too
print(adj)                       # [[1], [0, 2], [1], [4], [3]]

# the same list built from an adjacency matrix
M = [[1, 1, 0, 0, 0],
     [1, 1, 1, 0, 0],
     [0, 1, 1, 0, 0],
     [0, 0, 0, 1, 1],
     [0, 0, 0, 1, 1]]
adj2 = [[v for v in range(n) if M[u][v] == 1 and v != u] for u in range(n)]
print(adj2)                      # [[1], [0, 2], [1], [4], [3]]

For a directed edge u → v, you would only do adj[u].append(v).

The visited array, and why we cannot live without it

A graph, unlike a tree, has no "down" direction. In an undirected graph, if 1 lists 2 as a neighbour, then 2 also lists 1. Start at 1, go to 2, and 2 says "my neighbour 1 is waiting"… you go back to 1, then to 2 again, forever. A visited array (one True/False slot per node) breaks the loop: mark a node the moment you reach it, and never enter a marked node again.

Connected components

A connected component is a group of nodes where you can walk from any node to any other node using edges, and nothing outside the group is reachable. The picture above has 2 components: {1, 2, 3} and {4, 5}. "Province" in this problem is just another name for a connected component.

The two ways to walk a graph

from collections import deque

adj = [[1], [0, 2], [1], [4], [3]]
n = len(adj)

def dfs(u, visited, order):
    visited[u] = True                 # mark as soon as we arrive
    order.append(u)
    for v in adj[u]:
        if not visited[v]:
            dfs(v, visited, order)

def bfs(start, visited, order):
    visited[start] = True
    queue = deque([start])
    while queue:
        u = queue.popleft()
        order.append(u)
        for v in adj[u]:
            if not visited[v]:
                visited[v] = True     # mark when we put it in the queue
                queue.append(v)

seen = [False] * n
out = []
dfs(0, seen, out)
print(out)                            # [0, 1, 2]
seen = [False] * n
out = []
bfs(3, seen, out)
print(out)                            # [3, 4]

Notice that one call from node 0 reached only 0, 1, 2. It could not reach 3 or 4. That is exactly the fact this problem is built on.

Part A · Count provinces with DFS

LeetCode 547 · in the sheet it is also called "count number of components"

1The question in simple words

There are n cities. Some pairs have a direct road between them. Connection also passes through a middle city: if A is joined to B, and B is joined to C, then A and C count as connected too (indirectly, through B).

A province is a group of cities that are all connected to each other (directly or indirectly), with no city outside the group connected to them. Return how many provinces there are, which means how many separate groups.

The roads are given as an n × n grid called isConnected: isConnected[i][j] = 1 means city i and city j have a direct road, and 0 means they don't.

(1)—(2)—(3)        (4)—(5)

 group 1: 1, 2, 3     group 2: 4, 5
 answer = 2

        1  2  3  4  5
  1  [  1, 1, 0, 0, 0 ]
  2  [  1, 1, 1, 0, 0 ]
  3  [  0, 1, 1, 0, 0 ]
  4  [  0, 0, 0, 1, 1 ]
  5  [  0, 0, 0, 1, 1 ]

Cities 1 and 3 have no direct road (row 1, column 3 is 0), but both are joined to 2, so they still sit in the same province.

2What the constraints tell us

• 1 ≤ n ≤ 200 → at least one city, so the answer is at least 1. And n is small: an n × n matrix has at most 40,000 cells, so even reading every cell is cheap. An O(n²) solution is perfectly fine.
• isConnected[i][i] = 1 → every city is marked as joined to itself. This is the diagonal. It is not a real road, and our code must not get confused by it (we'll see that the visited check handles it).
• isConnected[i][j] = isConnected[j][i] → the matrix is symmetric, so the graph is undirected.
• Values are only 0 or 1 → no weights.
• n ≤ 200 also means a recursion at most 200 calls deep, well under Python's default limit of 1000. Recursive DFS is safe here.

3Intuition: how to think about it

Picture the cities as islands of houses, and you have a tin of paint. Pick any unpainted city and spill paint on it. The paint flows along every road to every city it can reach, directly or through others, and stops only where roads end. One spill paints one whole province.

Now walk past every city in order. Whenever you find one that is still unpainted, it must belong to a province you haven't touched yet, so spill paint again and add 1 to your count. When you have walked past every city, the number of spills is the number of provinces.

In code, "spilling paint" is one DFS call, and "painted" is the visited array.

4Building the logic from the teacher's example

Step 1: reading the matrix: each row is a list of children

The teacher reads the first row slowly: [1, 1, 0, 0, 0].

• 1st value is 1 → city 1 is joined to city 1, which is itself.
• 2nd value is 1 → city 1 is joined to city 2.
• 3rd, 4th, 5th are 0 → city 1 is not directly joined to 3, 4 or 5.

So row u is simply the list of children (neighbours) of node u, written as 0/1 flags. Row 2 is [1, 1, 1, 0, 0]: city 2 is joined to 1, to itself, and to 3.

Step 2: one DFS marks one whole group

Send city 1 into a DFS. The DFS has a single job: mark the node as visited, then go to each unvisited child and do the same. From 1 it reaches 2, and from 2 it reaches 3. Then nothing new is left, so the call ends. Visited is now {1, 2, 3}. It could not reach 4 or 5, because no road leads there.

Now make a second call from 4 (the teacher adds that starting from 5 would work just as well, since any unvisited city of that group will do). It marks 4 and then 5. Now every city is visited, after 2 calls. And there are 2 groups. That's no accident: number of fresh DFS calls = number of provinces.

Step 3: why must we mark visited? (the infinite loop)

Without marking: at 1 we go to child 2. Row 2 says 1 is a child of 2, so we go to 1. Row 1 says 2 is a child, so we go to 2… The calls bounce 1 → 2 → 1 → 2 forever (in Python this ends in a RecursionError). Marking 1 as visited before looking at its children stops 2 from going back.

Step 4: how big is the visited array, and how do we know n?

The matrix has one row per city, so n = len(isConnected). Make visited of size n, all False (the teacher uses an int array with 0/1 in Java; True/False is the same idea). Slot u says whether city u has been painted.

Step 5: which cities do we start a DFS from?

We don't know in advance how far one call will spread. So we try every city in order, but only call DFS if it is still unvisited:

• city 1: not visited → call DFS, count = 1. (This paints 1, 2, 3.)
• city 2: already visited by city 1's call → skip.
• city 3: already visited → skip.
• city 4: not visited → call DFS, count = 2. (This paints 4, 5.)
• city 5: already visited → skip.

Step 6: inside the DFS: which children can we enter?

In DFS(node), walk across row node with an index i from 0 to n−1. Enter i only if both:

1. isConnected[node][i] == 1, so there really is a road from node to i, and
2. visited[i] is False, so i is not painted yet.

5Approach steps

1. n = len(isConnected), visited = [False] * n, provinces = 0.
2. For every city i from 0 to n−1: if i is not visited, call dfs(i) and do provinces += 1.
3. dfs(node): mark visited[node] = True. Then for every i from 0 to n−1: if isConnected[node][i] == 1 and i is not visited, call dfs(i).
4. Return provinces.

6Code (Python)

class Solution:
    def findCircleNum(self, isConnected):
        n = len(isConnected)              # one row per city
        visited = [False] * n
        provinces = 0

        for i in range(n):
            if not visited[i]:            # a city no earlier call reached
                self.dfs(i, visited, isConnected)
                provinces += 1            # one new call = one new province
        return provinces

    def dfs(self, node, visited, isConnected):
        visited[node] = True              # mark first
        n = len(isConnected)              # n is not known in here, so read it again
        for i in range(n):                # walk across row "node"
            if isConnected[node][i] == 1 and not visited[i]:
                self.dfs(i, visited, isConnected)

The teacher hit an error on screen because her DFS function used n, which only existed in the main function. The fix was to read the length again inside DFS, as in the line marked above.

7Code line by line

8Dry run

The teacher's example, written with code indexes: cities 1..5 become 0..4. So the roads are 0–1, 1–2 and 3–4.

(0)—(1)—(2)        (3)—(4)

(0✓)—(1✓)—(2✓)     (3)—(4)
 provinces = 1

(0✓)—(1✓)—(2✓)     (3✓)—(4✓)
 provinces = 2

Two fresh calls were made, so the answer is 2 ✓.

9Complexity & remember

• Time O(n²). DFS runs exactly once per city in total, because visited stops repeats. Each run walks a whole row of n columns, whether the values are 0 or 1. So n cities × n columns = n². With n ≤ 200 that is at most 40,000 checks, far below the roughly 10⁸ operations that would cause TLE.
• Space O(n). The visited array is n. The recursion stack depends on the shape of the graph. In the example, the first call only grew 3 deep (0 → 1 → 2) even though there were 5 cities. In the worst case every city is in one province, joined like a chain, and the stack grows n deep. So the stack is also O(n).

Part B · Count provinces with BFS

The teacher's words: the only real job is to reach every node of a group and mark it visited. DFS does that, but so does BFS. The outer loop and the counting stay exactly the same. Only the "paint one province" function changes.

1The question

Same as Part A: count the groups in isConnected.

2Constraints

Same as Part A. One small bonus for BFS: it uses no recursion, so it never worries about Python's recursion limit, even if n were much bigger.

3Intuition: ripples instead of a deep dive

Instead of chasing one road as far as it goes, BFS paints the start city, then all its direct neighbours, then their neighbours, like a ripple spreading on water. It still stops when no new city can be reached, so one BFS still paints exactly one province.

4What changes, and the "when to mark" question

The teacher's recipe: create a queue and put the start node in it. To find the children, use the same row scan with the same if-check. But where DFS would make a recursive call, BFS just appends that child to the queue, so it gets processed later when it is popped.

5Approach steps

1. Same outer loop: for each unvisited city i, call bfs(i), then provinces += 1.
2. bfs(start): mark start, put it in a deque.
3. While the queue isn't empty: pop the front node, then scan its row. For every column i with a 1 that isn't visited: mark it and append it.

6Code (Python)

from collections import deque

class Solution:
    def findCircleNum(self, isConnected):
        n = len(isConnected)
        visited = [False] * n
        provinces = 0
        for i in range(n):
            if not visited[i]:
                self.bfs(i, visited, isConnected)
                provinces += 1
        return provinces

    def bfs(self, start, visited, isConnected):
        n = len(isConnected)
        visited[start] = True
        queue = deque([start])
        while queue:
            node = queue.popleft()
            for i in range(n):
                if isConnected[node][i] == 1 and not visited[i]:
                    visited[i] = True     # mark when pushed: never queued twice
                    queue.append(i)       # instead of a recursive call

7Code line by line (only the new lines)

8Dry run

Same graph: (0)—(1)—(2) (3)—(4).

9Complexity & remember

• Time O(n²): each city is popped once and its whole row is scanned. That's the same reasoning as DFS, so the teacher says the time is the same for both.
• Space O(n): the visited array plus a queue that never holds more than n cities.

Part C · Revision page

s = Solution()
print(s.findCircleNum([[1,1,0,0,0],[1,1,1,0,0],[0,1,1,0,0],[0,0,0,1,1],[0,0,0,1,1]]))  # 2
print(s.findCircleNum([[1,1,0],[1,1,0],[0,0,1]]))   # 2
print(s.findCircleNum([[1,0,0],[0,1,0],[0,0,1]]))   # 3
print(s.findCircleNum([[1,1,1],[1,1,1],[1,1,1]]))   # 1
print(s.findCircleNum([[1]]))                       # 1

Based on this video: Number of Provinces | Graph