Find Champion II

Leetcode Problem:

• Find Champion II

Summary

• Find the champion in a directed acyclic graph (DAG) tournament

Approach

• Use depth-first search (DFS) to traverse the graph and identify the champion team
• The champion team is the one that has no stronger team.

Complexity

• O(n + m) where n is the number of teams and m is the number of edges in the graph

Solution Code:

class Solution {
public:
    vector adj[101];
    set leaf;
    bool visited[101];
    set start;
    void dfs(int cur){
        if(visited[cur]) return;
        visited[cur] = true;
        if(adj[cur].size() == 0){
            leaf.insert(cur);
            return;
        }
        for(int i = 0 ; i < adj[cur].size(); i++){
            int next = adj[cur][i];
            dfs(next);
        }
    }
    int findChampion(int n, vector>& edges) {
        if (n == 1) return 0;
        for(int  i = 0 ; i < edges.size(); i++){
            int a = edges[i][0];
            int b = edges[i][1];
            adj[b].push_back(a);
            start.insert(a);
            start.insert(b);
        }
        if(n != start.size()){
            return -1;
        }
        for(auto iter = start.begin(); iter != start.end(); iter++){
            dfs(*iter);
        }
        if(leaf.size() == 1) return *(leaf.begin());
        return -1;
    }
};