3

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!

Salmaan P
  • 817
  • 1
  • 12
  • 32
  • This is not DFS... hint: your DFS function doesn't return anything. – Nir Alfasi Sep 05 '17 at 07:54
  • I'm changing the matrix in place. It works for smaller inputs. Can you please tell me where I'm off? – Salmaan P Sep 05 '17 at 08:00
  • How does changing the matrix help you find the number of connected components ? – Nir Alfasi Sep 05 '17 at 08:05
  • 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 Sep 05 '17 at 08:10
  • 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 https://leetcode.com/problems/friend-circles – Salmaan P Sep 05 '17 at 08:15

1 Answers1

2

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.

niemmi
  • 17,113
  • 7
  • 35
  • 42
  • 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? – Salmaan P Sep 05 '17 at 08:31
  • 1
    @SalmaanP The graph representation is called [adjacency matrix](https://en.wikipedia.org/wiki/Adjacency_matrix). What you were doing looks more like considering the edges as vertices. – niemmi Sep 05 '17 at 08:38
  • thanks, i see where I was confused. Would my method work on a normal matrix like shown here https://www.youtube.com/watch?v=R4Nh-EgWjyQ ? – Salmaan P Sep 05 '17 at 09:03
  • 1
    @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. – niemmi Sep 05 '17 at 09:17