题目：997. 找到小镇的法官

给你 n 个人的社交关系（你知道任意两个人之间是否认识），然后请你找出这些人中的「名人」。所谓「名人」有两个条件： 1、所有其他人都认识「名人」。 2、「名人」不认识任何其他人。 用图的说法：这个节点没有一条指向其他节点的有向边；且其他所有节点都有一条指向这个节点的有向边。

核心¶

// 可以直接调用，能够返回 i 是否认识 j
bool knows(int i, int j);

// 请你实现：返回「名人」的编号
int findCelebrity(int n) {
    // todo
}

一、暴力解法¶

cand 是候选人（candidate） 的缩写，我们的暴力算法就是从头开始穷举，把每个人都视为候选人，判断是否符合「名人」的条件。

class Solution {
public:
    int findCelebrity(int n) {
        for (int cand = 0; cand < n; cand++) {
            int other;
            for (other = 0; other < n; other++) {
                if (cand == other) continue;
                // 保证其他人都认识 cand，且 cand 不认识任何其他人
                // 否则 cand 就不可能是名人
                if (knows(cand, other) || !knows(other, cand)) {
                    break;
                }
            }
            if (other == n) {
                // 找到名人
                return cand;
            }
        }
        // 没有一个人符合名人特性
        return -1;
    }
};

二、优化解法¶

1. 排除候选人,Time-- O(N)¶

只要观察任意两个候选人的关系，我一定能确定其中的一个人不是名人，把他排除。不妨认为这两个人的编号分别是 cand 和 other，然后我们逐一分析每种情况，看看怎么排除掉一个人。对于情况一，cand 认识 other，所以 cand 肯定不是名人，排除。因为名人不可能认识别人。对于情况二，other 认识 cand，所以 other 肯定不是名人，排除。对于情况三，他俩互相认识，肯定都不是名人，可以随便排除一个。对于情况四，他俩互不认识，肯定都不是名人，可以随便排除一个。因为名人应该被所有其他人认识。

因此

if (knows(cand, other) || !knows(other, cand)) {
    // cand 不可能是名人
}
else {
    // other 不可能是名人
}

我们可以不断从候选人中选两个出来，然后排除掉一个，直到最后只剩下一个候选人，这时候再使用一个 for 循环判断这个候选人是否是货真价实的「名人」。

算法思路：将所有候选人装进queue里，每次弹出cand和other，排除掉一个再拿回来

2.空间复杂度优化O(N)变O（1）¶

三、另类/更优/更简洁解法：入度、出度¶

已知总人数为n，名人的入度为0，出度为n-1。遍历一遍关系算出每个人的出度、入度，over