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.
1#include <iostream>
2#include <vector>
3
4int findChampion(int n, const std::vector<std::pair<int, int>>& edges) {
5 std::vector<int> inDegree(n, 0);
6 for (const auto& edge : edges) {
7 inDegree[edge.second]++;
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
22int main() {
23 std::vector<std::pair<int, int>> edges = {{0, 1}, {1, 2}};
24 int result = findChampion(3, edges);
25 std::cout << "Champion: " << result << std::endl;
26 return 0;
27}
28Using C++, this solution employs a vector to keep the in-degree of nodes, iterates over all edges to calculate these values, then identifies a unique node with an in-degree of 0 as the champion if one exists.
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.
1using System;
2using System.Collections.Generic;
3
4public class Tournament {
5 private static void TopologicalSortUtil(int v, bool[] visited, Stack<int> stack, List<List<int>> adj) {
6 visited[v] = true;
7 foreach (int i in adj[v]) {
8 if (!visited[i])
9 TopologicalSortUtil(i, visited, stack, adj);
10 }
11 stack.Push(v);
12 }
13
14 public static int FindChampion(int n, int[][] edges) {
15 List<List<int>> adj = new List<List<int>>(n);
16 for (int i = 0; i < n; i++) adj.Add(new List<int>());
17 foreach (var edge in edges) {
18 adj[edge[0]].Add(edge[1]);
19 }
20 Stack<int> stack = new Stack<int>();
21 bool[] visited = new bool[n];
22 for (int i = 0; i < n; i++) {
23 if (!visited[i])
24 TopologicalSortUtil(i, visited, stack, adj);
25 }
26 int potentialChampion = stack.Pop();
27 foreach (int team in stack) {
28 if (!adj[potentialChampion].Contains(team))
29 return -1;
30 }
31 return potentialChampion;
32 }
33
34 public static void Main() {
35 int[][] edges = { new int[] { 0, 1 }, new int[] { 1, 2 } };
36 Console.WriteLine("Champion: " + FindChampion(3, edges));
37 }
38}
39This C# uses DFS to carry out topological sorting, storing results in a stack. The last element is checked for being a potential sole named champion.