In this approach, we calculate the in-degree for each node in the graph. The in-degree of a node is the number of edges that point to it. If a node has an in-degree of 0, it means no other node (team in this case) is stronger than it, making it a candidate for the champion. If exactly one such node exists, it is the unique champion. Otherwise, we return -1.
Time Complexity: O(n + m), where n is the number of nodes and m is the number of edges. Space Complexity: O(n), as we store the in-degree of each node.
1using System;
2
3public class Tournament {
4 public static int FindChampion(int n, int[][] edges) {
5 int[] inDegree = new int[n];
6 foreach (var edge in edges) {
7 inDegree[edge[1]]++;
8 }
9 int champion = -1;
10 for (int i = 0; i < n; i++) {
11 if (inDegree[i] == 0) {
12 if (champion == -1) {
13 champion = i;
14 } else {
15 return -1;
16 }
17 }
18 }
19 return champion;
20 }
21
22 public static void Main() {
23 int[][] edges = { new int[] { 0, 1 }, new int[] { 1, 2 } };
24 Console.WriteLine("Champion: " + FindChampion(3, edges));
25 }
26}
27This C# approach uses an array to manage node in-degrees and checks for zero in-degree nodes, marking a unique one as the champion if identified.
This approach uses topological sorting to find the last node in the order, presuming no other nodes are stronger. If multiple final nodes exist in the topological order, it implies multiple candidates, hence no unique champion can be determined.
Time Complexity: O(n + m). Space Complexity: O(n^2) due to adjacency matrix used for simplicity.
1#include <iostream>
2#include <vector>
3#include <stack>
4
5void topologicalSortUtil(int v, std::vector<bool>& visited, std::stack<int>& Stack, const std::vector<std::vector<int>>& adj) {
6 visited[v] = true;
7 for (int i : adj[v]) {
8 if (!visited[i])
9 topologicalSortUtil(i, visited, Stack, adj);
10 }
11 Stack.push(v);
12}
13
14int findChampion(int n, const std::vector<std::pair<int, int>>& edges) {
15 std::vector<std::vector<int>> adj(n);
16 for (const auto& edge : edges) {
17 adj[edge.first].push_back(edge.second);
18 }
19 std::stack<int> Stack;
20 std::vector<bool> visited(n, false);
21 for (int i = 0; i < n; i++) {
22 if (!visited[i])
23 topologicalSortUtil(i, visited, Stack, adj);
24 }
25 int potentialChampion = Stack.top();
26 Stack.pop();
27 while (!Stack.empty()) {
28 if (std::find(adj[potentialChampion].begin(), adj[potentialChampion].end(), Stack.top()) == adj[potentialChampion].end())
29 return -1;
30 Stack.pop();
31 }
32 return potentialChampion;
33}
34
35int main() {
36 std::vector<std::pair<int, int>> edges = {{0, 1}, {1, 2}};
37 int result = findChampion(3, edges);
38 std::cout << "Champion: " << result << std::endl;
39 return 0;
40}
41This C++ code uses topological sorting through DFS and stack data structure to identify the team at the end of sort order as a potential unique champion if valid.