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 <stdio.h>
2#include <stdbool.h>
3
4int findChampion(int n, int edges[][2], int edgesSize) {
5 int inDegree[n];
6 for (int i = 0; i < n; i++) inDegree[i] = 0;
7
8 for (int i = 0; i < edgesSize; i++) {
9 inDegree[edges[i][1]]++;
10 }
11
12 int champion = -1;
13 for (int i = 0; i < n; i++) {
14 if (inDegree[i] == 0) {
15 if (champion == -1) {
16 champion = i;
17 } else {
18 return -1; // More than one champion
19 }
20 }
21 }
22 return champion;
23}
24
25int main() {
26 int edges[][2] = {{0, 1}, {1, 2}};
27 int result = findChampion(3, edges, 2);
28 printf("Champion: %d\n", result);
29 return 0;
30}
31This C code snippet creates an array to store the in-degree of each team. It iterates over the edges, updating the in-degree of destination nodes. Finally, it checks for nodes with an in-degree of 0. If there's exactly one, it returns this as the 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.
1import java.util.*;
2
3public class Tournament {
4 private static void topologicalSortUtil(int v, boolean[] visited, Stack<Integer> stack, List<List<Integer>> adj) {
5 visited[v] = true;
6 for (int i : adj.get(v)) {
7 if (!visited[i])
8 topologicalSortUtil(i, visited, stack, adj);
9 }
10 stack.push(v);
11 }
12
13 public static int findChampion(int n, int[][] edges) {
14 List<List<Integer>> adj = new ArrayList<>();
15 for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
16 for (int[] edge : edges) {
17 adj.get(edge[0]).add(edge[1]);
18 }
19 Stack<Integer> stack = new Stack<>();
20 boolean[] visited = new boolean[n];
21 for (int i = 0; i < n; i++) {
22 if (!visited[i])
23 topologicalSortUtil(i, visited, stack, adj);
24 }
25 int potentialChampion = stack.pop();
26 while (!stack.isEmpty()) {
27 if (!adj.get(potentialChampion).contains(stack.peek()))
28 return -1;
29 stack.pop();
30 }
31 return potentialChampion;
32 }
33
34 public static void main(String[] args) {
35 int[][] edges = {{0, 1}, {1, 2}};
36 int result = findChampion(3, edges);
37 System.out.println("Champion: " + result);
38 }
39}
40This Java approach uses a DFS based topological sort stored in a stack, evaluating the final stack element for champion eligibility.