---
# System prepended metadata

title: 997. Find the Town Judge
tags: [Leetcode, python, c++, easy, graph]

---

###### tags: `Leetcode` `easy` `graph` `python` `c++`

# 997. Find the Town Judge

## [題目連結:] https://leetcode.com/problems/find-the-town-judge/

## 題目: 
In a town, there are n people labeled from ```1``` to ```n```. There is a rumor that one of these people is secretly the town judge.

If the town judge exists, then:

The town judge trusts nobody.

Everybody (except for the town judge) trusts the town judge.

There is exactly one person that satisfies properties **1** and **2**.

You are given an array trust where ```trust[i] = [ai, bi]``` representing that the person labeled ```ai``` trusts the person labeled ```bi```.

Return the label of the town judge if the town judge exists and can be identified, or return ```-1``` otherwise.

## 解題想法:
* 此題為求:
    * n個人
    * 是否有 **恰好一點** 
        * indegrees= n-1
        * outdegree= 0
    * ex: [1,2]: 表示 1->2 
        * **1**的outdegree+=1
        * **2**的indegree+=1

## Python:
* 其實可以不用建立graph，但我還是有用字典紀錄
``` python=
from collections import defaultdict
class Solution(object):
    def findJudge(self, n, trust):
        """
        :type n: int
        :type trust: List[List[int]]
        :rtype: int
        """
        graph=defaultdict(list)
        indegree=[0]*(n) #n=1 放在pos:0 記得要
        outdegree=[0]*(n)
        #connect the graph
        for u,v in trust:
            graph[u].append(v) #u->v
            indegree[v-1]+=1
            outdegree[u-1]+=1 
        for pos,val in enumerate(indegree):
            if val==n-1 and outdegree[pos]==0:
                return pos+1
        return -1        
```

## C++:
``` cpp=
class Solution {
public:
    int findJudge(int n, vector<vector<int>>& trust) {
        //unordered_map<int,vector<int>> graph;
        vector<int> indegree(n,0), outdegree(n,0);
        for (auto num: trust){
            //u=num[0], v=num[1]
            //graph[num[0]-1].push_back(num[1]-1);
            indegree[num[1]-1]+=1;
            outdegree[num[0]-1]+=1;
        }
        for (int i=0; i<n; i++){
            if (outdegree[i]==0 && indegree[i]==n-1)
                return i+1;
        }
        return -1;
    }
};
```