851. 喧闹和富有

image-20211215102759427

解题思路：

  • 这题主要是对拓扑排序的考察，因为题目要求的是拥有钱不少于person x，所以我们可以根据richer建立有向无环图deg,同时用vis存储对应入度数，即对于richer中每个关系rich来说，建立rich[0]到rich[1]的有向边，因此拓扑排序得到的结果就会是由富有->贫穷,而根据拓扑排序的结果，我们可以用当前遍历到的元素x的answer更新其相邻节点的answer，即若满足quiet[answer[x]] <quiet[answer[y]],则answer[y]=answer[x]。

以下为C++代码：

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
class Solution {
public:
    vector<int> loudAndRich(vector<vector<int>>& richer, vector<int>& quiet) {
       //拓扑排序例子：
        //拓扑排序使得每一条u->v,u都在v之前出现
        int n = quiet.size();
        vector<vector<int>> deg(n);
        vector<int> vis(n);

        //记录下当前的richer情况，绘制有向图
        for (vector<int>& rich : richer) {
            deg[rich[0]].push_back(rich[1]); //绘制有向边
            vis[rich[1]]++; //入度+1
        }

        queue<int> q;
        vector<int> ans(n);
        iota(ans.begin(), ans.end(), 0);//以自身为默认值，因为自己拥有的钱一定不少于自身
        //记录下当前入度为0的节点
        for (int i = 0; i < n; i++) {
            if (vis[i] == 0) {
                q.push(i);
            }
        }

        //进行拓扑排序
        while (!q.empty()) {
            int x = q.front();
            q.pop();
            //更新当前x对应的answer
            for (int y : deg[x]) {
                if (quiet[ans[x]] < quiet[ans[y]]) {
                    ans[y] = ans[x];
                }
                //更新入度
                if (--vis[y] == 0) {
                    q.push(y);
                }
            }
        }

        return ans;

    }
};