用c++编写n 个人一起玩狼人杀,按从 1 到 n 的顺序编号,据说,这群人当中有一个预言家。如果预言家真的存在,那么: 1)预言家不会信任任何人。 2)每个人(除了预言家)都信任预言家。 最多只有一个人同时满足 1 和 2 。 给定一个数组 trust ,其中 trust[i] = [ai, bi] 表示编号为 ai 的人信任编号为 bi 的人。如果预言家存在并且可以确定他的身份,请返回预言家的编号;否则,返回 -1 。 提示: 1 <= n <= 1000;0 <= trust.length <= 100;trust[i].length == 2;trust 中的所有trust[i] = [ai, bi] 互不相同;ai != bi;1 <= ai;bi <= n
时间: 2023-02-07 12:24:44 浏览: 197
c++狼人杀 c++狼人杀
4星 · 用户满意度95%
这是一道关于图论的题目。在这道题中,我们可以用一张有向图来表示这些人之间的信任关系,其中点表示人,边表示信任关系。
预言家的条件是: 1)不信任任何人,也就是没有出边; 2)所有人都信任他,也就是所有其他点都有一条指向他的边。
我们可以用一个数组来记录每个点的入度,然后遍历所有点,如果有一个点满足入度为 n-1,则返回这个点的编号。如果遍历完所有点仍然没有找到符合条件的点,则返回 -1。
代码如下:
```
int findJudge(int n, vector<vector<int>>& trust) {
vector<int> indegree(n+1, 0);
for (const auto& t : trust) {
indegree[t[0]]++;
}
for (int i = 1; i <= n; i++) {
if (indegree[i] == 0) return i;
}
return -1;
}
```
阅读全文