277. Find the Celebrity

O(n) time O(1) space
先扫描找出一个candidate再验证是不是真正的celebrity，只需要证明不会丢失真正的celebrity，因为所有人都会被check，真正的celebrity一定能成为candidate

// Forward declaration of the knows API.
bool knows(int a, int b);

class Solution {
public:
    int findCelebrity(int n) {
        int cand = 0;
        for (int i = 1; i < n; ++i) {
            // if (!knows(i, cand)) { // 理论上也可以
            if (knows(cand, i)) {
                cand = i;
            }
        }
        for (int i = 0; i < n; ++i) {
            if (i != cand && (knows(cand, i) || !knows(i, cand))) return -1;
        }
        return cand;
    }
};