Number of Provinces

You can find the number of provinces by identifying connected components in the graph. You can use Depth First Search (DFS) or Union-Find to achieve this.

Depth First Search (DFS) Approach

Here’s a code snippet that uses DFS to find the number of provinces:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution:
    def findCircleNum(self, isConnected: List[List[int]]) -> int:
        n = len(isConnected)
        visited = [False] * n
        
        def dfs(city):
            for neighbor in range(n):
                if isConnected[city][neighbor] == 1 and not visited[neighbor]:
                    visited[neighbor] = True
                    dfs(neighbor)
        
        provinces = 0
        for i in range(n):
            if not visited[i]:
                dfs(i)
                provinces += 1
                
        return provinces

Explanation

1. Initialization: Initialize a visited array with False to keep track of cities that have been visited.
2. DFS Function: The dfs function is defined to traverse through the connected cities. It visits a city and recursively calls itself for all its neighbors if they are not visited.
3. Counting Provinces: Iterate through all the cities. If a city is not visited, call the dfs function starting from that city, and increment the provinces counter.
4. Return Result: Finally, return the total number of provinces.

The time complexity of this approach is O(N^2), where N is the number of cities. In the worst case, we might need to visit all the pairs of cities. The space complexity is O(N) due to the visited array and recursive stack.

Problem Definition

Define the Terms

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

(i, j) are the vertices, we can lookup in the adjacency matrix if they are connected or not.

0 1 2 0 [1,1,0] 1 [1,1,0] 2 [0,0,1]

Province: Component

Transform the given problem into an abstract problem. We can reframe the question:

• How many components are there in the graph?

Ex2: Three vertices, no connections Number of components = 3 You can generalize this to 200 vertices.

Ex1: Three vertices, one connection Number of components = 2

Ex1’: Four vertices, one connection Number of components = 3

Ex3: Three vertices, two connections Number of components = 1

Ex4: Three vertices, three connections Number of components = 1

Define the Interface

  Input: array of arrays (adjacency matrix)
  Output: integer

Identify Implicit Inputs

Define the Goal

Return the total number of provinces.

Identify the Constraints

Constraints:

1 <= n <= 200 n == isConnected.length n == isConnected[i].length isConnected[i][j] is 1 or 0. isConnected[i][i] == 1 isConnected[i][j] == isConnected[j][i]

Determine the Scope

• List assumptions
• Define boundaries of the problem

Search the Problem Space

• Look for clues in the problem statement

Classify the Problem

• Decontextualize the Problem

• Can you think of this problem in a different way?

• Can you reframe it?

Problem Representation

• Analyze the Input and Output

• Analyze the Examples

Solve the Problem by Hand

Recognize the Pattern

Identify the Invariants

Brainstorm Solutions

• Brute Force Approach

  0 1 2 0 [1,1,0] 1 [1,1,0] 2 [0,0,1]

Start traversal from 1, you can reach 2. visited = [1, 1, 0] 0, 1, 2

We again start traversal from 3 and traverse all the nodes we have not visited already.

We needed to run the traversal twice. Number of components.

Iterate over all the nodes starting from node 1 mark it as visited

Worst case, we traverse every edge. The number of edges is equal to the number of vertices.

DFS BFS

T: O() S: O()

• Shortcomings

• Evaluate and Select Approach

Analyze Time and Space Complexity

• Time: O( )
• Space: O( )

Outline the Solution

Key Takeaways

Reflect

• What went right?

• What went wrong?

• What can we improve next time?

We start the dfs from index start. When do we stop the dfs? Stop the DFS when we have no more edges to follow.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

def dfs(is_connected, visited, start)
   for j in (0...is_connected.size)
     if is_connected[start][j] == 1 && visited[j] == 0
         visited[j] = 1
         dfs(is_connected, visited, j)
     end
   end
end

# @param {Integer[][]} is_connected
# @return {Integer}
def find_circle_num(is_connected)
   n = is_connected.size
   visited = [0] * n
   counter = 0
   
   for i in (0...n)
      if visited[i] == 0
          counter += 1
  
          dfs(is_connected, visited, i) 
      end
   end
   
   return counter
end

Identifying Problem Isomorphism

“Number of Provinces” is similar to a group of problems that solve “connected components” in an undirected graph using depth-first search (DFS), breadth-first search (BFS), or union-find algorithm.

A simpler problem than this is “Find the Town Judge”. In this problem, you are given trust relations between people in a town and need to find the town judge. It is simpler because it essentially boils down to finding a node with N-1 inward connections and zero outward connections, which can be solved using an array to track the number of trusts.

A more complex problem is “Critical Connections in a Network”. This problem is about finding all the critical connections in the network. A connection is critical if removing it will make some servers unable to reach some other servers. This problem is more complex because it requires an understanding of Tarjan’s algorithm, which is used to find articulation points in a graph.

The reasoning behind these choices:

• “Find the Town Judge” involves understanding the relationships between different nodes (people in this case), similar to understanding the friendship relationships in “Number of Provinces”. However, the structure of the problem is simpler because you just need to track the number of trusts, while in “Number of Provinces” you need to identify separate groups (provinces) of friends.

• “Critical Connections in a Network” involves identifying connected components in a network, like “Number of Provinces”. However, the “Critical Connections” problem requires a deeper understanding of graph algorithms to identify the critical connections that, if removed, would disconnect the network.

Thus, the order of problems from simpler to more complex, based on graph theory:

1. “Find the Town Judge”
2. “Number of Provinces”
3. “Critical Connections in a Network”

This mapping is approximate. While these problems share the common concept of relationships between nodes in a graph, the exact constraints and specifics vary, affecting the implementation of the solution.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution:
    def findCircleNum(self, M: List[List[int]]) -> int:
        if not M:
            return 0
        
        n = len(M)
        visit = [False]*n

        def dfs(u):
            for v in range(n):
                if M[u][v] ==1 and visit[v] == False:
                    visit[v] = True
                    dfs(v)

        count = 0
        for i in range(n):
            if visit[i] == False:
                count += 1
                visit[i] = True
                dfs(i)

        return count

Problem Classification

Graph Traversal

Language Agnostic Coding Drills

This is a depth-first search (DFS) problem in a graph, where each person is considered as a node. If person A knows person B, we draw an edge between nodes A and B. The main goal of the problem is to find the number of isolated groups. Here is the breakdown:

1. Working with 2D Lists (Matrix): Understand how to declare a 2D list, and how to access elements within it. Write a simple nested loop to iterate through a 2D list.

2. Understanding Boolean Values and Lists: Learn how to create a list of boolean values and manipulate those values.

3. Implementing Depth-First Search (DFS): Understand the concept of depth-first search (DFS), how it traverses through a graph, and write a simple DFS algorithm for a given graph.

4. Nested Function Calls: Understanding how nested function calls work and their scope.

5. Working with Graphs: Understand the basics of a graph data structure, how nodes are connected, and how to traverse them.

6. Defining Classes and Methods: Practice creating a class and defining methods within it.

Targeted Drills in Python

1. Working with 2D Lists (Matrix):

   1 2 3 4 5 6

   # Declare a 2D list matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]] # Print each element of the 2D list for row in matrix: for elem in row: print(elem)

2. Understanding Boolean Values and Lists:

   1 2 3 4 5

   # Declare a list with boolean values bool_list = [False, True, False, True] # Change the value of the second element to False bool_list[1] = False print(bool_list) # Output: [False, False, False, True]

3. Implementing Depth-First Search (DFS):

   1 2 3 4 5 6 7 8 9 10 11

   graph = {'A': ['B', 'C'], 'B': ['A', 'D', 'E'], 'C': ['A', 'F'], 'D': ['B'], 'E': ['B', 'F'], 'F': ['C', 'E']} visited = set() def dfs(visited, graph, node): if node not in visited: print (node) visited.add(node) for neighbour in graph[node]: dfs(visited, graph, neighbour) dfs(visited, graph, 'A') # Output: 'A' 'B' 'D' 'E' 'F' 'C'

4. Nested Function Calls:

   1 2 3 4 5 6

   def outer_function(x): def inner_function(y): return y + 1 return inner_function(x) * 2 print(outer_function(3)) # Output: 8

5. Working with Graphs:

   1 2 3 4

   graph = {'A': ['B', 'C'], 'B': ['A', 'D', 'E'], 'C': ['A', 'F'], 'D': ['B'], 'E': ['B', 'F'], 'F': ['C', 'E']} # Print each node and its neighbours for node in graph: print(node, ":", graph[node])

6. Defining Classes and Methods:

   1 2 3 4 5 6

   class MyClass: def my_method(self, x): return x * 2 obj = MyClass() print(obj.my_method(3)) # Output: 6