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.
1def find_champion(n, edges):
2 in_degree = [0] * n
3 for u, v in edges:
4 in_degree[v] += 1
5 champion = -1
6 for i in range(n):
7 if in_degree[i] == 0:
8 if champion == -1:
9 champion = i
10 else:
11 return -1
12 return champion
13
14print(find_champion(3, [[0, 1], [1, 2]]))
15In this Python solution, we use a list to count in-degrees, then it checks for nodes with zero in-degrees, identifying a single such node 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.
1function topologicalSort(n, adj) {
2 let visited = new Array(n).fill(false);
3 let stack = [];
4
5 function dfs(v) {
6 visited[v] = true;
7 for (let i of adj[v]) {
8 if (!visited[i]) {
9 dfs(i);
10 }
11 }
12 stack.push(v);
13 }
14
15 for (let i = 0; i < n; i++) {
16 if (!visited[i]) {
17 dfs(i);
18 }
19 }
20 return stack;
21}
22
23function findChampion(n, edges) {
24 let adj = Array.from({ length: n }, () => []);
25 for (let [u, v] of edges) {
26 adj[u].push(v);
27 }
28 let stack = topologicalSort(n, adj);
29 let potentialChampion = stack.pop();
30
31 for (let team of stack) {
32 if (!adj[potentialChampion].includes(team))
33 return -1;
34 }
35 return potentialChampion;
36}
37
38console.log(findChampion(3, [[0, 1], [1, 2]]));
39This JavaScript solution involves topological sorting via DFS, where the last node in the sort order is a candidate for titleholder, subject to verification.