문제 링크

내 코드

Indegree 개수 세기

0ms, 93.22MB

class Solution {
public:
    int findChampion(int n, vector<vector<int>>& edges) {
        vector<int> inDegree(n, 0);
        // topological sort
        for(auto& edge : edges) {
            int u = edge[0], v = edge[1]; // u -> v
            inDegree[v]++;
        }

        int answer{-1};
        for(int v{};v<n;++v) {
            if(inDegree[v] == 0) {
                if(answer != -1) return -1;
                answer = v;
            }
        }
        return answer;
    }
};

Solution

Approach: In-degree Count

• 52ms, 104.90MB
• Complexity
  • Here, N is the number of teams given, and M is the number of edges.
  • Time Complexity: $O(N + M)$
  • Space Complexity: $O(N)$

class Solution {
public:
    int findChampion(int n, vector<vector<int>>& edges) {
        vector<int> indegree(n, 0);
        // Store the indegree of each team.
        for (auto edge : edges) {
            indegree[edge[1]]++;
        }

        int champ = -1, champCount = 0;
        for (int i = 0; i < n; i++) {
            // If the team can be chamption, store the number and count of such
            // teams.
            if (indegree[i] == 0) {
                champCount++;
                champ = i;
            }
        }

        // If more than one champion, return -1 else return the team number.
        return champCount > 1 ? -1 : champ;
    }
};