547. Friend Circles (Medium)
There are N students in a class. Some of them are friends, while some are not. Their friendship is transitive in nature. For example, if A is a direct friend of B, and B is a direct friend of C, then A is an indirect friend of C. And we defined a friend circle is a group of students who are direct or indirect friends.
Given a N*N matrix M representing the friend relationship between students in the class. If M[i][j] = 1, then the ith and jth students are direct friends with each other, otherwise not. And you have to output the total number of friend circles among all the students.
Example 1:
Input:
[[1,1,0],
[1,1,0],
[0,0,1]]
Output: 2
Explanation:The 0th and 1st students are direct friends, so they are in a friend circle.
The 2nd student himself is in a friend circle. So return 2.
Example 2:
Input:
[[1,1,0],
[1,1,1],
[0,1,1]]
Output: 1
Explanation:The 0th and 1st students are direct friends, the 1st and 2nd students are direct friends,
so the 0th and 2nd students are indirect friends. All of them are in the same friend circle, so return 1.
Note:
- N is in range [1,200].
- M[i][i] = 1 for all students.
- If M[i][j] = 1, then M[j][i] = 1.
Summary
There are N students in a class. Some of them are friends, while some are not. Their friendship is transitive in nature. For example, if A is a direct friend of B, and B is a direct friend of C, then A is an indirect friend of C. And we defined a friend circle is a group of students who are direct or indirect friends. Given a N*N matrix M representing the friend relationship between students in the class. If M[i][j] = 1, then the ith and jth students are direct friends with each other, otherwise not. And you have to output the total number of friend circles among all the students.
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:
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.
c++ 22ms
class Solution {
void dfs(vector<vector<int>>& M, vector<bool>& visited, int i) {
for (int j = 0; j < M.size(); ++j) {
if (M[i][j] == 1 && !visited[j]) {
visited[j] = true;
dfs(M, visited, j);
}
}
}
public:
int findCircleNum(vector<vector<int>>& M) {
vector<bool> visited(M.size(),false);
int cnt = 0;
for (int i = 0; i < M.size(); ++i) {
if (!visited[i]) {
dfs(M, visited, i);
++cnt;
}
}
return cnt;
}
};
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:
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.
c++ 25ms
class Solution {
public:
int findCircleNum(vector<vector<int>>& M) {
vector<int> visited(M.size(),false);
queue<int> q;
int cnt = 0;
for (int i = 0; i < M.size(); ++i) {
if (!visited[i]) {
q.push(i);
while (!q.empty()) {
int t = q.front(); q.pop();
visited[t] = true;
for (int j = 0; j < M.size(); ++j) {
if (M[t][j] && !visited[j]) q.push(j);
}
}
++cnt;
}
}
return cnt;
}
};
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 nn 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 -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[parent[x]]=parent[y]$$, which ultimately combines them into the same group.
The following animation depicts the process for a simple matrix:
c++ 29ms
class Solution {
int find(int x) {
if (root[x] == -1) return x;
return find(root[x]);
}
void Union(int x, int y) {
int rx = find(x), ry = find(y);
if (rx != ry) root[rx] = ry;
}
public:
int findCircleNum(vector<vector<int>>& M) {
root = vector<int>(M.size(),-1);
for (int i = 0; i < M.size(); ++i) {
for (int j = 0; j < M.size(); ++j) {
if (M[i][j] && i != j) {
Union(i, j);
}
}
}
int cnt = 0;
for (auto& a: root) {
if (a == -1) ++cnt;
}
return cnt;
}
private:
vector<int> root;
};
Complexity Analysis
- Time complexity: $$O(n^2)$$. 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.