[leetcode题解]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.

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:

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

一个班中分帮结派,我们要找到总共有多少个小圈子,题目给出一个矩阵,说明一个班中的同学两两之间是否是朋友,如果A和B是朋友,B和C也是朋友那A和C也是朋友,把所有是朋友的人分成一组,查看总共有多少组。

看到题目就能知道可以直接使用并查集进行解决,而且是非常标准的并查集即可,先按照关系矩阵建立并查集,最后扫描数组,其祖先为自己的就说明是一个独立的小组,进行统计即可。

c代码如下;

#define N 205

void init(int *pre, int n) {
    int i = 0;
    
    for (i = 0; i < n; i++) {
        pre[i] = i;
    }
}

int root(int *pre, int x) {
    if (x != pre[x])
        return root(pre, pre[x]);
    return x;
}

void merge(int *pre, int x, int y) {
    int fx = 0, fy = 0;
    
    fx = root(pre, x);
    fy = root(pre, y);
    
    if (fx != fy)
        pre[fx] = fy;
}

int findCircleNum(int** M, int MRowSize, int MColSize) {
    int pre[N];
    int i = 0;
    int j = 0;
    int res = 0;
    
    init(pre, N);
    for (i = 0; i < MRowSize; i++) {
        for (j = 0; j < MColSize; j++) {
            if (M[i][j] == 1)
                merge(pre, i, j);
        }
    }
    
    for (i = 0; i < MRowSize; i++) {
        if (pre[i] == i)
            ++res;
    }
    return res;
}

本文遵从CC3.0协议转载请注明:转自凌风技术站

本文标题:[leetcode题解]547. Friend Circles,朋友圈

本文链接地址:http://www.iaccepted.net/algorithm/leetcode/158.html

相关文章