mediumGraphsPure DSA~20 min
Find the Universally Trusted Authority
Among n participants, an authority is trusted by everyone else but trusts no one. Given the trust relations, identify the authority, or report there is none.
Problem
In a town of n people (1..n), the judge trusts nobody, everybody (except the judge) trusts the judge, and exactly one person fits this. Given trust where trust[i] = [a, b] means a trusts b, return the judge's label, or -1 if no judge exists.
Input
An integer n and a list trust of [a, b] directed trust pairs.
Output
An integer: the judge's label, or -1.
Constraints
- 1 <= n <= 1000
- 0 <= trust.length <= 10^4
- All trust pairs are unique; a != b.
Examples
Example 1
Input
n = 3, trust = [[1,3],[2,3]]
Output
3
Person 3 is trusted by 1 and 2 and trusts no one.
Example 2
Input
n = 3, trust = [[1,3],[2,3],[3,1]]
Output
-1
Person 3 trusts person 1, so cannot be the judge.