|
| 1 | +#!/usr/bin/python3 |
| 2 | +""" |
| 3 | +In a town, there are N people labelled from 1 to N. There is a rumor that one |
| 4 | +of these people is secretly the town judge. |
| 5 | +
|
| 6 | +If the town judge exists, then: |
| 7 | +
|
| 8 | +The town judge trusts nobody. |
| 9 | +Everybody (except for the town judge) trusts the town judge. |
| 10 | +There is exactly one person that satisfies properties 1 and 2. |
| 11 | +You are given trust, an array of pairs trust[i] = [a, b] representing that the |
| 12 | +person labelled a trusts the person labelled b. |
| 13 | +
|
| 14 | +If the town judge exists and can be identified, return the label of the town |
| 15 | +judge. Otherwise, return -1. |
| 16 | +
|
| 17 | +Example 1: |
| 18 | +
|
| 19 | +Input: N = 2, trust = [[1,2]] |
| 20 | +Output: 2 |
| 21 | +Example 2: |
| 22 | +
|
| 23 | +Input: N = 3, trust = [[1,3],[2,3]] |
| 24 | +Output: 3 |
| 25 | +Example 3: |
| 26 | +
|
| 27 | +Input: N = 3, trust = [[1,3],[2,3],[3,1]] |
| 28 | +Output: -1 |
| 29 | +Example 4: |
| 30 | +
|
| 31 | +Input: N = 3, trust = [[1,2],[2,3]] |
| 32 | +Output: -1 |
| 33 | +Example 5: |
| 34 | +
|
| 35 | +Input: N = 4, trust = [[1,3],[1,4],[2,3],[2,4],[4,3]] |
| 36 | +Output: 3 |
| 37 | +
|
| 38 | +
|
| 39 | +Note: |
| 40 | +
|
| 41 | +1 <= N <= 1000 |
| 42 | +trust.length <= 10000 |
| 43 | +trust[i] are all different |
| 44 | +trust[i][0] != trust[i][1] |
| 45 | +1 <= trust[i][0], trust[i][1] <= N |
| 46 | +""" |
| 47 | +fromtypingimportList |
| 48 | +fromcollectionsimportdefaultdict |
| 49 | + |
| 50 | + |
| 51 | +classSolution: |
| 52 | +deffindJudge(self,N:int,trust:List[List[int]])->int: |
| 53 | +""" |
| 54 | + like the find the celebrity |
| 55 | + """ |
| 56 | +ingress=defaultdict(set) |
| 57 | +egress=defaultdict(set) |
| 58 | +forp,qintrust: |
| 59 | +egress[p].add(q) |
| 60 | +ingress[q].add(p) |
| 61 | +foriinrange(1,N+1): |
| 62 | +iflen(egress[i])==0andlen(ingress[i])==N-1: |
| 63 | +returni |
| 64 | +return-1 |