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!

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.