Reference: LeetCode
Difficulty: Medium

Problem

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.

Note:

  • N is in range [1,200].
  • M[i][i] = 1 for all students.
  • If M[i][j] = 1, then M[j][i] = 1.

Example: 

1
2
3
4
5
6
7
8
9
10
11
Input: 
[[1,1,0],
 [1,1,0],
 [0,0,1]]
Output: 2

Input: 
[[1,1,0],
 [1,1,1],
 [0,1,1]]
Output: 1

Analysis

DFS

Treat M as an adjacency matrix of a graph.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// treat this matrix as an adjacency matrix
public int findCircleNum(int[][] M) {
  // Assume M is not null
  int n = M.length;
  boolean[] marked = new boolean[n];
  int numComponent = 0;
  for (int i = 0; i < n; ++i) {
    if (marked[i] == false) {
      ++numComponent;
      dfs(i, marked, M);
    }
  }
  return numComponent;
}

private void dfs(int v, boolean[] marked, int[][] M) {
  marked[v] = true; // visit
  for (int w = 0; w < M[v].length; ++w) {
    if (w == v || M[v][w] == 0) continue;
    if (marked[w] == false) {
      dfs(w, marked, M);
    }
  }
}

Time: $O(N^2) = O(N + M) = O(N + N^2)$ for a dense graph.
Space: $O(N)$ for marked array.