Leetcode 997:找到小镇的法官

题目描述

在一个小镇里，按从1到N标记了N个人。传言称，这些人有一个是小镇上的秘密法官。如果小镇的法官真的存在，那么：

1. 小镇的法官不相信任何人
2. 每个人（除了小镇法官外）都信任小镇的法官
3. 只有一个人同时满足属性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 = 5，trust=[[1，3]，[1，4]，[2，3]，[2，4]，[4，3]]

输出：3

 

解题思路

刚读完本题，感觉可以使用并查集解决，但是分析到示例4和示例5发现与并查集不太一样，示例4说明本题的"信任"不具有传递性，也就是1信任2，2信任3，不能说明1信任3；示例5表明一个人可以信任多个人。所以考虑将原本并查集算法中的int数组换成vector数组，记录每一个人的father。

int findJudge(int N, vector<vector<int>>& trust) {
        vector<int> vect[N+1];
        for(int i=0;i<trust.size();i++){
            vect[trust[i][0]].push_back(trust[i][1]);
        }
        int fa = 0,sum = 0;
        for(int i=1;i<=N;i++){
            if(vect[i].size() == 0){
                fa = i;
                sum++;
            }
        }
        if(sum != 1) return -1;
        for(int i=1;i<=N;i++){
            if(i != fa){
                if(count(vect[i].begin(),vect[i].end(),fa) == 0) return -1;
            }
        }
        return fa;
    }