Find Champion II

class Solution {
public:
    int determineWinner(int n, vector<vector<int>>& links) {
        vector<int> incomingEdges(n, 0);
        for (auto link : links) {
            incomingEdges[link[1]]++;
        }

        int winner = -1, potentialWinners = 0;
        for (int i = 0; i < n; i++) {
            if (incomingEdges[i] == 0) {
                potentialWinners++;
                winner = i;
            }
        }

        return potentialWinners > 1 ? -1 : winner;
    }
};

This C++ program provides a solution to find a "champion" or winner from a list of competitors based on a directed graph approach where each competitor is represented as a node and each competitive relationship as a directed edge. Here's a breakdown of how the solution handles the problem:

• The function determineWinner accepts two parameters: an integer n representing the total number of competitors and a 2D vector links where each sub-vector contains two integers representing a directed edge from the first competitor to the second, indicating that the second competitor has beaten the first.
• An integer vector incomingEdges keeps a count of incoming edges (beat paths) for each competitor. This is initialized to zero for all competitors.
• The function iterates over each link (competitive relationship) and increments the count of incoming edges for competitors who have been defeated as depicted by the links.
• After establishing the number of defeats each competitor has, the code iterates through the incomingEdges vector to determine competitors with no defeats (incomingEdges[i] == 0).
• The code identifies if there is exactly one competitor with zero defeats. If not, it returns -1, indicating no clear champion or multiple potential champions. If there is exactly one, it returns the index of that competitor, marking them as the winner.

In essence, the solution checks for a node (competitor) in a directed graph that has no incoming edges, which means no other node is directed towards it, implying no defeats. If there's only one such node, it's the champion; otherwise, there's a conflict in determining a unique winner.

public class Solution {

    public int findWinner(int teamCount, int[][] relationships) {
        // Track number of incoming edges for each team
        int[] incomingEdges = new int[teamCount];

        // Increment incoming edges count for each team
        for (int[] relation : relationships) {
            incomingEdges[relation[1]]++;
        }

        int winner = -1;
        int singleWinnerCount = 0;

        // Check each team for zero incoming edges
        for (int team = 0; team < teamCount; team++) {
            if (incomingEdges[team] == 0) {
                singleWinnerCount++;
                winner = team;
            }
        }

        // Determine if there is a unique winner
        return singleWinnerCount > 1 ? -1 : winner;
    }
}

The provided Java solution detects the winner in a scenario where multiple teams are compared based on their relationships. The function findWinner accepts the total number of teams and a list of relationships between them, determining who could potentially be the champion.

Here's how the solution operates:

• An array incomingEdges is initialized to track the number of incoming relationships (defeats) each team has from other teams in the form of directed edges.
• As each relationship is processed, the method increments the count of incoming edges for the team that was defeated.
• After processing all relationships, the program searches for the team with zero incoming edges, which indicates no defeats, naming it as the potential winner.
• If exactly one team is found with zero incoming edges, it is declared the winner. If more than one such team exists, indicating no clear winner, the function returns -1.

Ensure that the input (number of teams and relationships) is correctly formatted to avoid errors during the array operations. This solution efficiently handles delineating the potential winner in a simple and understandable manner.

class Solution:
    def determineChampion(self, total_teams: int, relations: list[list[int]]) -> int:
        team_incoming_edges = [0] * total_teams
        for relation in relations:
            team_incoming_edges[relation[1]] += 1

        potential_champion = -1
        champions_found = 0

        for team_id in range(total_teams):
            if team_incoming_edges[team_id] == 0:
                champions_found += 1
                potential_champion = team_id
        
        return potential_champion if champions_found == 1 else -1

Solution summary for finding a champion from a number of teams based on their relationships, implemented in Python:

• The code defines a class Solution with the method determineChampion, which takes total_teams (an integer that represents the number of teams) and relations (a list of lists, where each sub-list has two integers representing a directional relationship from one team to another).
• Begin by initializing an array team_incoming_edges with zeros, sized by total_teams. This array tracks the number of direct losses each team has; a loss is indicated by another team pointing to a team in the relations.
• Loop through each relation, incrementing the incoming edge count for teams that have been defeated as indicated by the second element in each sub-list in relations.
• Establish default values for potential_champion as -1 and champions_found as 0.
• Iterate through teams by their indices. If a team has no incoming losses (team_incoming_edges[team_id] == 0), it's a candidate for champion, increment champions_found and update potential_champion with the current team_id.
• If exactly one champion candidate is found (champions_found == 1), return the potential_champion. Otherwise, return -1 indicating no unique champion is determined.

This code effectively identifies if there is a unique team that does not have any defeats. If multiple undefeated teams exist or all teams have been defeated, it returns -1 to indicate the absence of a unique champion.