Solution

Approach #1 Using Depth First Search[Accepted]

Algorithm

The given matrix can be viewed as the Adjacency Matrix of a graph. By viewing the matrix in such a manner, our problem reduces to the problem of finding the number of connected components in an undirected graph. In order to understand the above statement, consider the example matrix below:

M= [1 1 0 0 0 0

    1 1 0 0 0 0

    0 0 1 1 1 0

    0 0 1 1 0 0

    0 0 1 0 1 0

    0 0 0 0 0 1]

If we view this matrix M as the adjancency matrix of a graph, the following graph is formed:

In this graph, the node numbers represent the indices in the matrix M and an edge exists between the nodes numbered $$i$$ and $$j$$ , if there is a 1 at the corresponding $$M[i][j]$$ .

In order to find the number of connected components in an undirected graph, one of the simplest methods is to make use of Depth First Search starting from every node. We make use of $$visited$$ array of size $$N$$ ( $$M$$ is of size $$NxN$$ ). This $$visited[i]$$ element is used to indicate that the $$i^{th}$$ node has already been visited while undergoing a Depth First Search from some node.

To undergo DFS, we pick up a node and visit all its directly connected nodes. But, as soon as we visit any of those nodes, we recursively apply the same process to them as well. Thus, we try to go as deeper into the levels of the graph as possible starting from a current node first, leaving the other direct neighbour nodes to be visited later on.

The depth first search for an arbitrary graph is shown below:

!?!../Documents/547_Friend_Circles_dfs.json:1000,563!?!

From the graph, we can see that the components which are connected can be reached starting from any single node of the connected group. Thus, to find the number of connected components, we start from every node which isn't visited right now and apply DFS starting with it. We increment the $$count$$ of connected components for every new starting node.

Complexity Analysis

• Time complexity : $$O(n^2)$$ . The complete matrix of size $$n^2$$ is traversed.

• Space complexity : $$O(n)$$ . $$visited$$ array of size $$n$$ is used.

Approach #2 Using Breadth First Search[Accepted]

Algorithm

As discussed in the above method, if we view the given matrix as an adjacency matrix of a graph, we can use graph algorithms easily to find the number of connected components. This approach makes use of Breadth First Search for a graph.

In case of Breadth First Search, we start from a particular node and visit all its directly connected nodes first. After all the direct neighbours have been visited, we apply the same process to the neighbour nodes as well. Thus, we exhaust the nodes of a graph on a level by level basis. An example of Breadth First Search is shown below:

!?!../Documents/547_Friend_Circles_bfs.json:1000,563!?!

In this case also, we apply BFS starting from one of the nodes. We make use of a $$visited$$ array to keep a track of the already visited nodes. We increment the $$count$$ of connected components whenever we need to start off with a new node as the root node for applying BFS which hasn't been already visited.

Complexity Analysis

• Time complexity : $$O(n^2)$$ . The complete matrix of size $$n^2$$ is traversed.

• Space complexity : $$O(n)$$ . A $$queue$$ and $$visited$$ array of size $$n$$ is used.

Approach #3 Using Union-Find Method[Accepted]

Algorithm

Another method that can be used to determine the number of connected components in a graph is the union find method. The method is simple.

We make use of a $$parent$$ array of size $$N$$ . We traverse over all the nodes of the graph. For every node traversed, we traverse over all the nodes directly connected to it and assign them to a single group which is represented by their $$parent$$ node. This process is called forming a $$union$$ . Every group has a single $$parent$$ node, whose own parent is given by $$\text{-1}$$ .

For every new pair of nodes found, we look for the parents of both the nodes. If the parents nodes are the same, it indicates that they have already been united into the same group. If the parent nodes differ, it means they are yet to be united. Thus, for the pair of nodes $$(x, y)$$ , while forming the union, we assign $$parent\big[parent[x]\big]=parent[y]$$ , which ultimately combines them into the same group.

The following animation depicts the process for a simple matrix:

!?!../Documents/547_Friend_Circles_dfs.json:1000,563!?!

At the end, we find the number of groups, or the number of parent nodes. Such nodes have their parents indicated by a $$\text{-1}$$ . This gives us the required count.

Complexity Analysis

• Time complexity : $$O(n^3)$$ . We traverse over the complete matrix once. Union and find operations take $$O(n)$$ time in the worst case.
• Space complexity : $$O(n)$$ . $$parent$$ array of size $$n$$ is used.

Analysis written by: @vinod23