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.
1function findChampion(n, edges) {
2 let inDegree = new Array(n).fill(0);
3 for (let [u, v] of edges) {
4 inDegree[v]++;
5 }
6 let champion = -1;
7 for (let i = 0; i < n; i++) {
8 if (inDegree[i] == 0) {
9 if (champion === -1) {
10 champion = i;
11 } else {
12 return -1;
13 }
14 }
15 }
16 return champion;
17}
18
19console.log(findChampion(3, [[0, 1], [1, 2]]));
20This JavaScript solution works similarly by using an array to track the in-degrees and determining if there is a unique node with zero in-degrees to confirm it 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.
1#include <stdio.h>
2#include <stdlib.h>
3
4void topologicalSortUtil(int v, int visited[], int *stack, int *index, int adj[][100], int n) {
5 visited[v] = 1;
6 for (int i = 0; i < n; i++) {
7 if (adj[v][i] && !visited[i]) {
8 topologicalSortUtil(i, visited, stack, index, adj, n);
9 }
10 }
11 stack[(*index)--] = v;
12}
13
14int topologicalSort(int n, int edges[][2], int edgesSize) {
15 int adj[100][100] = {0};
16 for (int i = 0; i < edgesSize; i++) {
17 adj[edges[i][0]][edges[i][1]] = 1;
18 }
19 int visited[100] = {0};
20 int stack[100];
21 int index = n - 1;
22 for (int i = 0; i < n; i++) {
23 if (!visited[i])
24 topologicalSortUtil(i, visited, stack, &index, adj, n);
25 }
26 int potentialChampion = stack[n - 1];
27 for (int i = 0; i < n - 1; i++) {
28 if (!adj[potentialChampion][stack[i]])
29 return -1;
30 }
31 return potentialChampion;
32}
33
34int main() {
35 int edges[][2] = {{0, 1}, {1, 2}};
36 int result = topologicalSort(3, edges, 2);
37 printf("Champion: %d\n", result);
38 return 0;
39}
40This C implementation uses DFS for topological sorting to find the potential champion, verifying it by checking if it's stronger than all other remaining teams.