LeetCode-547:朋友圈（中等）

LeetCode-547. 朋友圈

难度：中等

问题描述

班上有 N 名学生。其中有些人是朋友，有些则不是。他们的友谊具有是传递性。如果已知 A 是 B 的朋友，B 是 C 的朋友，那么我们可以认为 A 也是 C 的朋友。所谓的朋友圈，是指所有朋友的集合。

给定一个 N * N 的矩阵 M，表示班级中学生之间的朋友关系。如果M[i][j] = 1，表示已知第 i 个和 j 个学生 互为 朋友关系，否则为不知道。你必须输出所有学生中的已知的朋友圈总数。

样例输入输出

示例1:

1
2
3
4
5
6
7
输入：
[[1,1,0],
 [1,1,0],
 [0,0,1]]
输出：2 
解释：已知学生 0 和学生 1 互为朋友，他们在一个朋友圈。
第2个学生自己在一个朋友圈。所以返回 2 。

示例2：

1
2
3
4
5
6
输入：
[[1,1,0],
 [1,1,1],
 [0,1,1]]
输出：1
解释：已知学生 0 和学生 1 互为朋友，学生 1 和学生 2 互为朋友，所以学生 0 和学生 2 也是朋友，所以他们三个在一个朋友圈，返回 1 。

提示：

  • 1 <= N <= 200
  • M[i][i] == 1
  • M[i][j] == M[j][i]

分析

首先分析输入数据，是无向图的邻接矩阵表示。找朋友圈个数也就是找该无向图中不同连通块的个数。

对于图的遍历，一般可以利用深度优先搜索(Depth First Search)、广度优先搜索(Breadth First Search)来解决。对于此问题，由于涉及分类、合并集合，还可以应用并查集(Union-Find Sets)。

深度优先搜索 DFS

深搜的过程：对于 i，j (0到N-1)，当前任务是找 i 的朋友，如果M[i][j] == 1 (代表 i 和 j 是朋友)，并且 j 没有被访问过，则标记 j 已访问，递归进行下一次深搜，找 j 的朋友；否则， j 自增直到 N-1，如此一直找到 i 所有的朋友都被标记。

所以，可以让 i 从0到 N-1 遍历，如果 i 没有被标记过，则继续递归深搜，并且记录朋友圈数加一。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int findCircleNum(vector<vector<int>>& M) {
        int N = M.size();
        vector<int> visited(N, 0);
        int count = 0;
        for(int i = 0; i < N; ++i) {
            if(visited[i] == 0) {
                dfs(M, visited, i, N);
                ++count;
            }
        }
        return count;
    }

    void dfs(vector<vector<int>>& M, vector<int>& visited, int i, int N) {
        for(int j = 0; j < N; ++j) {
            if(M[i][j] == 1 && visited[j] == 0) {
                visited[j] = 1;
                dfs(M, visited, j, N);
            }
        }
    }
};

时间复杂度：O(n2)

空间复杂度：O(n)

广度优先搜索 BFS

广搜和深搜思路差不多，只不过标记的顺序是按层次来的。利用队列就可以解决。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    int findCircleNum(vector<vector<int>>& M) {
        int N = M.size();
        vector<int> visited(N, 0);
        int count = 0;
        queue<int> q;
        for(int i = 0; i < N; ++i) {
            if (visited[i] == 0) {
                q.push(i);
                while (!q.empty()) {
                    int s = q.front();
                    q.pop();
                    visited[s] = 1;
                    for (int j = 0; j < N; ++j) {
                        if (M[s][j] == 1 && visited[j] == 0)
                            q.push(j);
                    }
                }
                ++count;
            }
        }
        return count;
    }

};

时间复杂度：O(n2)

空间复杂度：O(n)

并查集 Union-Find Sets

刚开始，有 N 个朋友圈，每个人一个朋友圈。如果两个人是朋友，就进行一次Merge（合并）操作，如果Merge成功，则朋友圈数量减一。最后的朋友圈数量就是需要的结果。

并查集需要实现两个方法，一个是Find，另一个是Merge。

Find(x) 用于查找x的根父节点。Merge(u, v) 判断u和v是否可以合并，如果可以，则合并u和v，返回True，否则返回False。

Find方法可以基于一个一维数组parent实现，使用路径压缩来优化。

1
2
3
4
5
6
7
8
9
10
11
12
int find(int x, vector<int>& parent) {
    int r = x;
    while(parent[r] != r) {
        r = parent[r];
    }
    while(parent[x] != x) {
        int t = parent[x];
        parent[x] = r;
        x = t;
    }
    return x;
}

Merge方法很简单，利用Find来实现即可：

1
2
3
4
5
6
7
8
9
bool merge(int u, int v, vector<int>& parent) {
    int ru = find(u);
    int rv = find(v);
    if (ru == rv) {
        return false;
    }
    parent[ru] = rv;
    return true;
}

准备工作时，需要对parent数组进行初始化：

1
2
3
4
5
6
void init(vector<int>& parent, int N) {
    parent.resize(N);
    for (int i = 0; i < N; i++) {
        parent[i] = i;
    }
}

最后的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
class Solution {
private:
    int find(int x) {
        int r = x;
        while(parent[r] != r) {
            r = parent[r];
        }
        while(parent[x] != x) {
            int t = parent[x];
            parent[x] = r;
            x = t;
        }
        return x;
    }

    bool merge(int u, int v) {
        int ru = find(u);
        int rv = find(v);
        if (ru == rv) {
            return false;
        }
        parent[ru] = rv;
        return true;
    }

    void init(int N) {
        parent.resize(N);
        for (int i = 0; i < N; i++) {
            parent[i] = i;
        }
    }
    
    vector<int> parent;
public:

    int findCircleNum(vector<vector<int>>& M) {
        int N = M.size();
        int ans = N;
        init(N);
        for (int i = 0; i < N; ++i) {
            for (int j = i+1; j < N; ++j) {
                if (M[i][j] && merge(i, j)) {
                    ans --;
                }
            }
        }
        return ans;
    }
};

上面的for循环是优化后的，考虑到无向图的邻接矩阵对角线对称，只用考虑一半即可。

时间复杂度：O(n2)

空间复杂度：O(n)

总结

本题不算难，但是可以使用多种算法去解决，值得思考，值得作为练手题。

本博客采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议(CC BY-NC-SA 4.0) 发布.
转载请注明转自 Lazy_V's Blog
Page View
⬆︎TOP