Leetcode #277. Find the Celebrity

[yokostan]

/* 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) {
        if (n == 0) return -1;
        if (n == 1) return 0;
        int a = 0;
        for (int i = 1; i < n; i++) {
            if (knows(a, i)) a = i;
        }
        
       for (int i = 0; i < n; i++) {
           if (i != a && knows(a, i) || !knows(i, a)) return -1;
       }
       return a;
    }
}

This is very much like the sheep influencer problem in CS161! In first pass we find the root that we can reach the furthest(if there is an influencer or source, then that one must be the only one). Then in second pass we gonna check whether our picked sheep is actually an influencer!