# Calculate complexity of algorithm and approach

The problem you are trying to solve is called counting the connected-components of a graph.

However, which graph are we talking about? Is it:

• the grid, where each cell of the square matrix is a node in the graph, adjacent to the adjacent cells;
• the graph whose adjacency matrix is this square matrix?

Consider for instance the following matrix:

``````[[1,1,0,1],
[1,1,0,0],
[0,0,1,0],
[1,0,0,1]]
``````

Your algorithm counts 5 groups in this matrix. This is expected because there are visually five groups in the grid:

``````[[A,A,0,B],
[A,A,0,0],
[0,0,C,0],
[D,0,0,E]]
``````

However, this matrix is the adjacency matrix of the following graph:

``````0 - 1
|
3   2
``````

Which, as you can see, only has two groups {0, 1, 3} and {2}.

## How to fix it

As far as I can see, your algorithm works perfectly to count the number of connected components in the grid. But that is not what you are interested in. You are interested in the number of connected components in the graph represented by this adjacency matrix. You can keep your functions `groupcheck` and `countGroup`, whose logic is good, but you should modify them so that a node of the graph is given by just one index `i` rather than by a pair of indices `(i,j)`; and so that two nodes `i` and `j` are considered adjacent by `groupcheck` if there is a 1 in `matrix[i][j]`.

Your function `groupcheck` currently “erases” cells which have already be counted by setting their value to 0 with the line `matrix[i][j] = 0`.

I suggest replacing this by maintaining a set of unseen nodes.

``````def groupcheck(i, matrix, unseen):
for j in range(len(matrix)):
if (j in unseen) and matrix[i][j]:  # if i and j are adjacent
groupcheck(j, matrix, unseen)

def countGroup(matrix):
count = 0
unseen = set(range(len(matrix)))
while unseen:
i = unseen.pop()
count += 1
groupcheck(i, matrix, unseen)
return count
``````

Complexity analysis: the complexity of `countGroup` is `n` times the complexity of `groupcheck`. Unfortunately, `groupcheck` can make up to `n` recursive calls, and each recursive call contains a `for`-loop, so the complexity of `groupcheck` is `O(n^2)`.