1st, 2018/05/10* BB -> DFS/BFS/Union Find
547 Friend Circles
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.
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.
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.
N is in range [1,200].
M[i][i] = 1 for all students.
If M[i][j] = 1, then M[j][i] = 1.
DFS {
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 ofvisitedvisitedarray of sizeNN(MMis of sizeNxNNxN). Thisvisited[i]visited[i]element is used to indicate that thei^{th}ithnode 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.
}
class Solution {
public int findCircleNum(int[][] M) {
if (M == null || M.length == 0) {
return 0;
}
int n = M.length;
int[] visited = new int[n];
int ans = 0;
for (int i = 0; i < n; i++) {
if (visited[i] == 0) {
dfs(M, visited, i);
ans++;
}
}
return ans;
}
public void dfs(int[][] M, int[] visited, int i) {
for (int j = 0; j < M.length; j++) {
if (M[i][j] == 1 && visited[j] == 0) {
visited[j] = 1;
dfs(M, visited, j);
}
}
}
}
BFS{
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:
}
class Solution {
public int findCircleNum(int[][] M) {
if (M == null || M.length == 0) {
return 0;
}
int n = M.length;
int[] visited = new int[n];
Queue<Integer> queue = new LinkedList<>();
int count = 0;
for (int i = 0; i < n; i++) {
if(visited[i] == 0) {
queue.offer(i);
while (!queue.isEmpty()) {
int head = queue.poll();
visited[head] = 1;
for (int j = 0; j < n; j++) {
if(M[head][j] == 1 && visited[j] == 0) {
queue.offer(j);
}
}
}
count++;
}
}
return count;
}
}
Approach #3 Using Union-Find Method[Accepted]
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 NN. 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}-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]parent[parent[x]]=parent[y], which ultimately combines them into the same group.
The following animation depicts the process for a simple matrix:
class Solution {
public int findCircleNum(int[][] M) {
if (M == null || M.length == 0) {
return 0;
}
int[] parent = new int[M.length];
for (int i = 0; i < parent.length; i++) {
parent[i] = -1;
}
for(int i = 0; i < M.length; i++) {
for (int j = 0; j < M[0].length; j++) {
if (M[i][j] == 1 && i != j) {
union(parent, i, j);
}
}
}
int count = 0;
for (int i = 0; i < parent.length; i++) {
if (parent[i] == -1) {
count++;
}
}
return count;
}
public void union (int[] parent, int x, int y) {
int newX = find(parent, x);
int newY = find(parent, y);
if (newX != newY) {
parent[newX] = newY;
}
}
public int find(int[]parent, int x) {
while (parent[x] != -1) {
x = parent[x];
}
return x;
}
}