Trusted by All, Trusts None

Easy

A village has n residents numbered from 1 to n. Rumor has it that one of them is an **arbiter**: someone who trusts nobody, yet is trusted by every other resident. You get a list trusts where trusts[i] = [a, b] means resident a trusts resident b. No other trust relations exist. Return the arbiter's number, or -1 if there is no such person.

Example 1

n=4, trusts=[[1, 2], [3, 2], [4, 2], [4, 1]] → 2

All three others trust person 2, and person 2 trusts nobody.

Example 2

n=3, trusts=[[1, 3], [2, 3], [3, 2]] → -1

Person 3 is trusted by everyone else, but trusts person 2.

Example 3

n=2, trusts=[] → -1

Constraints

1 ≤ n ≤ 1000
0 ≤ len(trusts) ≤ 10⁴
trusts[i] = [a, b], 1 ≤ a, b ≤ n, a ≠ b
All pairs in trusts are distinct

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Graph Array Hash Table

Similar problems

Which Machine to Cure Hard Which Machine to Unplug Hard Videos at a Friendship Distance Medium Dishes You Can Cook Medium Rooms Open from the Hall Medium

Input

n=4, trusts=[[1, 2], [3, 2], [4, 2], [4, 1]]

Expected

Run checks the first 3 tests in your browser. Submit checks all 89 tests on the server, hidden ones included.