/**
1.暴力: 记录所有点的出度和入度, 找到入度 == n, 出度 == 1的点
    1.1 优化因为"名人"只有一个, 如果一条边是连通的, 那就顺着这条边向下找, 找到的最后一个点的入度必定是0, 

2. 分析下给定的api, 分为两种情况
    2.1 a!=b && knows(a, b) == true,  a知道b,   那么a一定不是名人
    2.2 a!=b && knows(a, b) == false, a不知道b, 那么b一定不是名人
    2.3 因为"名人"最多只有一个, 所以可以从左右向中间找, 验证下剩下的一个是不是"名人"即可
*/

/* The knows API is defined in the parent class Relation.
      boolean knows(int a, int b); */

public class Solution extends Relation {
    public int findCelebrity(int n) {
        // return degree(n);
        return exclude(n);
    }

    private int degree(int n){
        int candidate = 0;
        for (int i = 1 ; i < n ; i++)
            if (knows(candidate, i))  candidate = i;

        return isStar(candidate, n);
    }

    private int exclude(int n){
        int i = 0, j = n-1;
        while (i < j) {
            if (knows(i, j)) i++;
            else             j--;
        }

        return isStar(i, n);
    }

    private int isStar(int x, int n){
        for (int i = 0;i < n ; i ++)
            if (x != i && (knows(x, i) || !knows(i, x)))
                return -1;
        return x;
    }
}