LeetCode/Find the Town Judge

인자로 주어지는 n명의 사람들 중 한 명이 judge이고 n-1명은 이 사람을 믿는다. 는 것이 맞으면 해당 사람의 번호를 return하고 조건에 부합하지 않으면 -1을 return하는 문제.

vector 2개를 둬서 등징횟수 세는 용도, 믿는 count 세는 용도로 쓴다.

judge는 아무도 믿지 않으므로 등장횟수는 0, 믿음 받은 count는 자기 자신을 제외한 마을 사람들 모두 이므로 n-1이 되어야 한다. 위 조건에 해당하지 않으면 judge가 없으므로 -1이다.

class Solution {
public:
    int findJudge(int n, vector<vector<int>>& trust) {
        //idea is to count indegree of each vertices
        //if indegree is n-1 means its a judge
        vector<int>indegree(n+1,0);
        vector<int>outdegree(n+1,0);
        
        if(trust.size()==0 && n==1)
            return true;
        
        for(int i=0;i<trust.size();i++)
        {
            indegree[trust[i][1]]++;
            outdegree[trust[i][0]]++;     
        }
        
        for(int i=0;i<n+1;i++)
        {
            if(indegree[i]==n-1 && outdegree[i]==0)
                return i;
        }
        return -1;
    }
};