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.
1import java.util.*;
2
3public class Tournament {
4 public static int findChampion(int n, int[][] edges) {
5 int[] inDegree = new int[n];
6 for (int[] edge : 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(String[] args) {
23 int[][] edges = {{0, 1}, {1, 2}};
24 int result = findChampion(3, edges);
25 System.out.println("Champion: " + result);
26 }
27}
28The Java version leverages an integer array to track in-degrees: each team’s in-degree gets incremented according to the input edges, before evaluating to find a possible unique champion.
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.
1def topological_sort(n, adj):
2 visited = [False] * n
3 stack = []
4 def dfs(v):
5 visited[v] = True
6 for i in adj[v]:
7 if not visited[i]:
8 dfs(i)
9 stack.append(v)
10
11 for i in range(n):
12 if not visited[i]:
13 dfs(i)
14 return stack
15
16
17def find_champion(n, edges):
18 adj = [[] for _ in range(n)]
19 for u, v in edges:
20 adj[u].append(v)
21 stack = topological_sort(n, adj)
22 potential_champion = stack[-1]
23 for team in stack[:-1]:
24 if potential_champion not in adj[team]:
25 return -1
26 return potential_champion
27
28print(find_champion(3, [[0, 1], [1, 2]]))
29In Python, this solution leverages a DFS-based topological sort and checks if the final level node in the sort order implies a single champion if valid.