Optimizing DFS in python

Question

I'm learning algorithms and was doing this problem which is finding the number of regions. I tried a depth first search approach using python but I am getting a call stack exceeded error. Can anyone tell me whats the flaw in my implementation and how to overcome it? The code is:

def findCircleNum(A):
 count = 0
 def dfs(row, column):
 if row < 0 or column >= len(A[0]) or row >= len(A) or column < 0:
 return
 if A[row][column] == 0:
 return
 A[row][column] = 0
 for i in range(row-1, row+2):
 if i >= 0 and i<len(A) and A[i][column] == 1:
 dfs(i, column)
 for i in range(column-1, column+2):
 if i >= 0 and i<len(A[0]) and A[row][i] == 1:
 dfs(row, i)
 for row in range(len(A)):
 for column in range(len(A[0])):
 if A[row][column] == 1:
 dfs(row, column)
 count += 1
 return count
findCircleNum(m)

The input it fails on is a 100x100 matrix of all 1's

The error is get is :

RuntimeError: maximum recursion depth exceeded

Thanks!

• Nir Alfasi: This is not DFS... hint: your DFS function doesn't return anything.
• Salmaan P: I'm changing the matrix in place. It works for smaller inputs. Can you please tell me where I'm off?
• Nir Alfasi: How does changing the matrix help you find the number of connected components ?
• Salmaan P: if the cell is a 1, i make it a 0 and then do DFS on it's neighbors. Changing it makes sure that the same cell isn't encountered again. hope that makes sense.
• Salmaan P: I'm sorry, I should have said independent components instead of connected components. Its finding the number of regions in the matrix. After the first dfs call is fully completed, all directly connected 1's will be made 0 which makes this one component at which point i increment count. This link has the full problem statement leetcode.com/problems/friend-circles

Answer 1

Why not just do a standard DFS while tracking the visited vertices (students) with a set? The problem statement says that maximum size of matrix is 200x200 so you wouldn't have to worry about the recursion limit assuming it is 1000. Using a set for tracking would also make the code simpler:

def findCircleNum(A):
 count = 0
 visited = set()
 def dfs(student):
 if student in visited:
 return
 visited.add(student)
 for i, friend in enumerate(A[student]):
 if friend:
 dfs(i)
 for student in range(len(A)):
 # Note we want to track circles, student without any friend won't count
 if student not in visited and any(A[student]):
 dfs(student)
 count += 1
 return count

EDIT The code in question looks like it's considering edges as vertices while doing DFS. This would also explain the issue with recursion depth since undirected graph of 100 vertices with loops but no multiedges has maximum (100 * 101) / 2 = 5050 edges.

• Salmaan P: okay, I get it now. I am manually looking at every cell and doing a DFS on its neighbours when we can take the full row since it works like adjacency list. Just curious, is what I did proper DFS or is it a wrong implementation?
• niemmi: @SalmaanP The graph representation is called adjacency matrix. What you were doing looks more like considering the edges as vertices.
• Salmaan P: thanks, i see where I was confused. Would my method work on a normal matrix like shown here youtube.com/watch?v=R4Nh-EgWjyQ ?
• niemmi: @SalmaanP With a quick glance it looks like it would have solved the problem described in a video. But do note that LeetCode problem is completely different kind although they both have binary matrix as input.