欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Leetcode 997:找到小镇的法官

程序员文章站 2022-05-21 15:05:46
...

题目描述

在一个小镇里,按从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;
    }