[LeetCode] 2924. Find Champion II

https://leetcode.com/problems/find-champion-ii/description/

leetcode - Find Champion II

문제 유형: 그래프

문제 난이도: Medium

 

문제

There are n teams numbered from 0 to n - 1 in a tournament; each team is also a node in a DAG.

You are given the integer n and a 0-indexed 2D integer array edges of length m representing the DAG, where edges[i] = [ui, vi] indicates that there is a directed edge from team ui to team vi in the graph.

A directed edge from a to b in the graph means that team a is stronger than team b and team b is weaker than team a.

Team a will be the champion of the tournament if there is no team b that is stronger than team a.

Return the team that will be the champion of the tournament if there is a unique champion, otherwise, return -1.

 

정수 n이 주어집니다.

DAG의 간선으로 팀들의 관계가 주어집니다.

[u, v]꼴에서 u는 v팀보다 강합니다.

 

최종 우승팀을 구하시오. 단, 우승자가 여럿이면 -1을 반환하시오,.

 

풀이

간선을 읽고 진입차수를 계산해서 진입차수가 0인 노드를 반환한다.

그러나 0인 노드가 둘 이상이라면 -1을 반환한다.

 

코드

C++

class Solution {
public:
    int findChampion(int n, vector<vector<int>>& edges) {
        vector<int> indegree(n, 0);

        for(const auto &edge : edges) {
            int dst = edge[1];
            indegree[dst]++;
        }

        int champion = -1;
        for(int i = 0; i < n; ++i) {
            if(indegree[i] == 0){
                if(champion != -1) return -1;
                champion = i;
            }
        }
        
        return champion;
    }
};