48找到小镇的法官（997）

作者: Turbo时间限制: 1S章节: DS:图

晚于: 2020-08-05 12:00:00后提交分数乘系数50%

截止日期: 2020-08-12 12:00:00

问题描述 :

在一个小镇里，按从 1 到 N 标记了 N 个人。传言称，这些人中有一个是小镇上的秘密法官。

如果小镇的法官真的存在，那么：

小镇的法官不相信任何人。

每个人（除了小镇法官外）都信任小镇的法官。

只有一个人同时满足属性 1 和属性 2 。

给定数组 trust，该数组由信任对 trust[i] = [a, b] 组成，表示标记为 a 的人信任标记为 b 的人。

如果小镇存在秘密法官并且可以确定他的身份，请返回该法官的标记。否则，返回 -1。

示例 1：

输入：N = 2, trust = [[1,2]]

输出：2

示例 2：

输入：N = 3, trust = [[1,3],[2,3]]

输出：3

示例 3：

输入：N = 3, trust = [[1,3],[2,3],[3,1]]

输出：-1

示例 4：

输入：N = 3, trust = [[1,2],[2,3]]

输出：-1

示例 5：

输入：N = 4, trust = [[1,3],[1,4],[2,3],[2,4],[4,3]]

输出：3

可使用以下main函数：

int main()

{

    int N,M;

    vector<vector<int> > trust;

    cin>>N>>M;

    int p1,p2;

    for(int i=0; i<M; i++)

    {

        cin>>p1>>p2;

        vector<int> oneTrust;

        oneTrust.push_back(p1);

        oneTrust.push_back(p2);

        trust.push_back(oneTrust);

    }

    int res=Solution().findJudge(N, trust);

    cout<<res<<endl;

}

输入说明 :

首先输入人的个数N和信任数组trust的大小M，

然后输入M行，每行两个整数a,、b，表示标记为 a 的人信任标记为 b 的人，a和b不相同。

说明：

1 <= N <= 1000

M <= 10000

1 <= a, b <= N

输出说明 :

输出一个整数，为法官的标记。如果无法确定法官，则输出-1。

输入范例 :

4 5 1 3 1 4 2 3 2 4 4 3

输出范例 :

3

#include <iostream>
#include <vector> 
using namespace std;
class Solution {
public:
    int findJudge(int N, vector<vector<int>>& trust) 
    {
        int flag[10000]={0};
        for(auto temp:trust)
        {
            flag[temp[1]]++;
            flag[temp[0]]--;
        }
        for(int i=1;i<=N;i++)
        {
            if(flag[i]==N-1) 
                return i;
        } 
        
        return -1;
    }
};
int main()
{
    int N,M;
    vector<vector<int> > trust;
    cin>>N>>M;
    int p1,p2;
    for(int i=0; i<M; i++)
    {
        cin>>p1>>p2;
        vector<int> oneTrust;
        oneTrust.push_back(p1);
        oneTrust.push_back(p2);
        trust.push_back(oneTrust);
    }
    int res=Solution().findJudge(N, trust);
    cout<<res<<endl;
}