LeetCode题解547.friend-circles-en

Problem

https://leetcode.com/problems/friend-circles/

Problem Description

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.

Solution

We can view a given matrix as Adjacency Matrix of a graph. In this case,
this problem become to find number of connected components in a undirected graph.

For example, how to transfer Adjacency Matrix into a graph problem. As below pic:

LeetCode题解547.friend-circles-en

Connected components in a graph problem usually can be solved using DFS, BFS, Union-Find.

Below we will explain details on each approach.

Approach #1. DFS

  1. Do DFS starting from every node, use visited array to mark visited node.
  2. For each node DFS, visit all its directly connected nodes.
  3. For each node DFS, DFS search will search all connected nodes, thus we count one DFS as one connected component.

as below pic show DFS traverse process:

LeetCode题解547.friend-circles-en

Complexity Analysis

  • Time Complexity: O(n*n) - n is the number of students, traverse n*n matrix
  • Space Complexity: O(n) - visited array of size n

Approach #2. BFS (Level traverse)

  1. Start from one node, visit all its directly connected nodes, or visit all nodes in the same level.
  2. Use visited array to mark already visited nodes.
  3. Increment count when start with a new node.

as below pic show BFS (Level traverse) traverse process:

LeetCode题解547.friend-circles-en

Complexity Analysis

  • Time Complexity: O(n*n) - n is the number of students, traverse n*n matrix
  • Space Complexity: O(n) - queue and visited array of size n

Approach #3. Union-Find

Determine number of connected components, Union Find is good algorithm to use.

Use parent array, for every node, all its directly connected nodes will be union,
so that two connected nodes have the same parent. After traversal all nodes, we just need to calculate
the number of different values in parent array.

For each union, total count minus 1, after traversal and union all connected nodes, simply
return counts.

Here use weighted-union-find to reduce union and find methods operation time.

To know more details and implementations, see further reading lists.

as below Union-Find approach process:

LeetCode题解547.friend-circles-en

Note: here using weighted-union-find to avoid Union and Find take O(n) in the worst case.

Complexity Analysis

  • Time Complexity: O(n*n*log(n) - traverse n*n matrix, weighted-union-find, union and find takes log(n) time complexity.
  • Space Complexity: O(n) - parent and rank array of size n

Key Points

  1. Transform Adjacency matrix into Graph
  2. Notice that it actually is to find number of connected components problem.
  3. Connected components problem approaches (DFS, BFS, Union-Find).

Code (Java)

Java code - DFS

class FindCirclesDFS {
  public int findCircleNumDFS(int[][] M) {
    if (M == null || M.length == 0 || M[0].length == 0) return 0;
    int n = M.length;
    int numCircles = 0;
    boolean[] visited = new boolean[n];
    for (int i = 0; i < n; i++) {
      if (!visited[i]) {
        dfs(M, i, visited, n);
        numCircles++;
      }
    }
    return numCircles;
  }

  private void dfs(int[][] M, int i, boolean[] visited, int n) {
    for (int j = 0; j < n; j++) {
      if (M[i][j] == 1 && !visited[j]) {
        visited[j] = true;
        dfs(M, j, visited, n);
      }
    }
  }
}

Java code - BFS

class FindCircleBFS {
  public int findCircleNumBFS(int[][] M) {
    if (M == null || M.length == 0) return 0;
    int numCircle = 0;
    int n = M.length;
    boolean[] visited = new boolean[n];
    Queue<Integer> queue = new LinkedList<>();
    for (int i = 0; i < n; i++) {
      // already visited, skip
      if (visited[i]) continue;
      queue.add(i);
      while (!queue.isEmpty()) {
        int curr = queue.poll();
        visited[curr] = true;
        for (int j = 0; j < n; j++) {
          if (M[curr][j] == 1 && !visited[j]) {
            queue.add(j);
          }
        }
      }
      numCircle++;
    }
    return numCircle;
  }
}

Java code - Union-Find

class FindCircleUF {
 public int findCircleNumUF(int[][] M) {
    if (M == null || M.length == 0 || M[0].length == 0) return 0;
    int n = M.length;
    UnionFind uf = new UnionFind(n);
    for (int i = 0; i < n - 1; i++) {
      for (int j = i + 1; j < n; j++) {
        // union friends
        if (M[i][j] == 1) {
          uf.union(i, j);
        }
      }
    }
    return uf.count;
  }
}

class UnionFind {
  int count;
  int[] parent;
  int[] rank;

  public UnionFind(int n) {
    count = n;
    parent = new int[n];
    rank = new int[n];
    for (int i = 0; i < n; i++) {
      parent[i] = i;
    }
  }

  public int find(int a) {
    return parent[a] == a ? a : find(parent[a]);
  }

  public void union(int a, int b) {
    int rootA = find(a);
    int rootB = find(b);
    if (rootA == rootB) return;
    if (rank[rootA] <= rank[rootB]) {
      parent[rootA] = rootB;
      rank[rootB] += rank[rootA];
    } else {
      parent[rootB] = rootA;
      rank[rootA] += rank[rootB];
    }
    count--;
  }

  public int count() {
    return count;
  }
}

References (Further reading)

  1. Adjacency Matrix Wiki
  2. Union-Find Wiki
  3. Algorighms 4 union-find

Similar Problems

  1. 323. Number of Connected Components in an Undirected Graph
  2. 1101. The Earliest Moment When Everyone Become Friends
LeetCode题解474.ones-and-zeros-en

Problem https://leetcode.com/problems/ones-and-zeroes/ Problem Description In the computer world, use restricted resource you have to generate maximum benefit is what we always wan…

LeetCode题解多人运动

已知小猪每晚都要约好几个女生到酒店房间。每个女生 i 与小猪约好的时间由 [si , ei］表示，其中 si 表示女生进入房间的时间， ei 表示女生离开房间的时间。由于小猪心胸开阔，思想开明，不同女生可以同时存在于小猪的房间。请计算出小猪最多同时在做几人的「多人运动」。例子： Input ： [[ 0 , 30] ,[ 5 , 10 ] ， [15 , 2…

LeetCode题解计算机为什么是基于二进制的？

可以是三进制么？二进制有什么好处？题解：为什么叫电子计算机？算盘应该没有二进制

LeetCode题解25.reverse-nodes-in-k-groups-en

Problem https://leetcode.com/problems/reverse-nodes-in-k-group/ Problem Description Given a linked list, reverse the nodes of a linked list k at a time and return its modified list…

LeetCode题解深度优先遍历和回溯的关系？

深度优先遍历的范围更大还是回溯的范围更大？为什么？题解：我的理解是：dfs是回溯思想的一种体现- 回溯：是在整个搜索空间中搜索出可行解，在搜索过程中不断剪枝回退，这是回溯的思想，这个搜索空间并没有限制于特定的数据结构。- dfs：dfs是指特定的数据结构中如图，树（特殊的图）中搜索答案，范围限制在了特定的数据结构。个人拙见。

推荐标签：,

腾讯的同事天天给我安利让我看《三体》，说马化腾和雷军也在…

腾讯的同事天天给我安利让我看《三体》，说马化腾和雷军也在看。自己强行看了两个月，全部给看完了。感觉这文笔也就我读初中的水平……而且写着国内的一些情况，外国人能理解吗？这书为什么会这么火？这水平我也可以去写呀[笑哭][笑哭][笑哭] 招商银行员工：可以写赶紧写一个啊，能拿科幻文学雨果奖。 包清白：哦 楼主：pei ！tui ！你也配姓龙 楼主：@赵龙王 呵呵 […]