Description
Given n people, a celebrity is known by everyone but knows no one. Using a knows(a, b) API, find the celebrity or return -1.
Examples
Input:
graph = [[1,1,0],[0,1,0],[1,1,1]]Output:
1Explanation:
Person 1 is celebrity.
Input:
graph = [[0,1,1,1],[0,0,0,0],[0,1,0,1],[0,1,0,0]]Output:
1Explanation:
Person 1 is the celebrity because everyone (persons 0, 2, and 3) knows person 1 (column 1 has all 1s except diagonal), but person 1 knows nobody (row 1 has all 0s). Person 1 satisfies both celebrity conditions.
Input:
graph = [[0,1],[1,0]]Output:
-1Explanation:
Neither person can be a celebrity. Person 0 knows person 1 but person 1 also knows person 0, so neither person knows nobody. For someone to be a celebrity, they must know no one while being known by everyone else.
Constraints
- •
2 ≤ n ≤ 100