Cacher is the code snippet organizer for pro developers

/*
A good way to answer this question in an interview is to work through three example on the whiteboard,
where you decide which edges you want to ask for, and then draw them as you go.
  1. The graph is a circle
  2. not everyone knows the candidate
  3. successful 

Note:
两个条件：（1）所有人都认识这个明星；（2）明星不认识所有人
*/

public class Solution extends Relation {
    int candidate = 0;
    public int findCelebrity(int n) {
        for(int i = 0; i < n; i++) {
            if(knows(candidate, i))
                candidate = i;
        }
        
        //check if it is real celebrity
        for(int i = 0; i < n; i++) {
            if((candidate != i && knows(candidate, i)) || !knows(i, candidate))
                return -1;
        }
        
        return candidate;
    }
}

public class Solution extends Relation {
    
    private int numberOfPeople;
    
    public int findCelebrity(int n) {
        numberOfPeople = n;
        for (int i = 0; i < n; i++) {
            if (isCelebrity(i)) {
                return i;
            }
        }
        return -1;
    }
    
    private boolean isCelebrity(int i) {
        for (int j = 0; j < numberOfPeople; j++) {
            if (i == j) continue; // Don't ask if they know themselves.
            if (knows(i, j) || !knows(j, i)) {
                return false;
            }
        }
        return true;
    }
}