find celebrity

这道题类似于997 find the town judge。
但可以采用graph的方法，topological的bfs方法，计算每个点的入度和出度，找出那个入读为n-1的就是解。
另一个种方法是find celebrity的方法，先定义i=0；遍历找出一个candidate， 再遍历判断是否这个candidate满足谁都认识他和他不认识任何人两个条件，如果可以100%确定就是他。
废话不说：coding：
方法1: 

1
2
3
4
5
6
7
8
9
10
11
int findJudge(int N, vector<vector<int>>& trust) {
  vector<vector<int>> knows(N + 1, vector<int>(N + 1));
  for (auto &t : trust) knows[t[0]][t[1]] = 1;
  return findCelebrity(N, knows);
}
int findCelebrity(int n, vector<vector<int>>& knows, int i = 1) {
  for (auto j = i + 1; j <= n; ++j) if (knows[i][j]) i = j;
  for (auto j = 1; j < i; ++j) if (knows[i][j]) return -1;
  for (auto j = 1; j <= n; ++j) if (i != j && !knows[j][i]) return -1;
  return i;
}

方法二：
directed graph：

1
2
3
4
5
6
7
8
9
int findJudge(int N, vector<vector<int>>& trust) {
        vector<int> count(N + 1, 0);
        for (auto& t : trust)
            count[t[0]]--, count[t[1]]++;
        for (int i = 1; i <= N; ++i) {
            if (count[i] == N - 1) return i;
        }
        return -1;
    }