챔피언 II 찾기

2924. 챔피언 II를 찾아보세요

난이도:중

주제: 그래프

토너먼트에는 0부터 n - 1까지 번호가 매겨진 n개의 팀이 있습니다. 각 팀은 DAG의 노드이기도 합니다.

정수 n과 DAG를 나타내는 길이가 m인 0-인덱스 2D 정수 배열 가장자리가 제공됩니다. 여기서 >dges[i] = [u _i, v_i]는 팀에서 방향성 우위가 있음을 나타냅니다. 그래프에서 u_i팀 v_i

그래프에서 a에서 b로의 방향성 간선은 A 팀이 b 팀보다 더 강하고, b 팀이 a 팀보다 약하다는 것을 의미합니다.

A팀보다 더 강한 B팀이 없다면 A팀이 이번 대회 챔피언이 될 것입니다.

고유 챔피언이 있으면 토너먼트의 챔피언이 될 팀을 반환하고, 그렇지 않으면 -1을 반환합니다.

메모

• 사이클은 일련의 노드 a1_{, a}2_{, ..., a}n_{, an 1} 즉, 노드 a₁은 노드와 동일한 노드입니다. a_{n 1}, 노드 a₁, a₂, ..., a_n이 구별되며 방향성이 있습니다. 범위 [1, n]. _DAG는 _사이클이 없는 유향 그래프입니다.
• 예 1:

입력:

n = 3, 가장자리 = [[0,1],[1,2]]

출력:
• 0
설명:
• 1팀이 0팀보다 약합니다. 2팀이 1팀보다 약합니다. 따라서 챔피언은 0팀입니다.
• 예 2:

입력:

n = 4, 가장자리 = [[0,2],[1,3],[1,2]]

출력:
• -1
설명:
• 2팀은 0팀, 1팀보다 약합니다. 3팀은 1팀보다 약합니다. 하지만 1팀과 0팀은 다른 어떤 팀보다 약하지 않습니다. 따라서 답은 -1입니다.
• 제약조건:

1 m == 가장자리.길이 0

가장자리[i].length == 2

0

가장자리[i][0] != 가장자리[i][1]

A팀이 B팀보다 강하면 B팀이 A팀보다 강하지 않도록 입력이 생성됩니다.

a팀이 b팀보다 강하고 b팀이 c팀보다 강하면 a팀이 c팀보다 강하다는 식으로 입력이 생성됩니다.

힌트:

1. 챔피언은 DAG에서 0등급이어야 합니다.

해결책:

주어진 DAG(방향성 비순환 그래프)에서 차수가 0인 팀을 식별해야 합니다. 들어오는 우위가 없는 팀은 다른 어떤 팀보다 강한 팀을 나타내므로 챔피언이 되기 위한 후보가 됩니다. 승률이 0인 팀이 정확히 하나만 있으면 해당 팀이 고유 챔피언이 됩니다. 해당 팀이 여러 개 있거나 없는 경우 결과는 -1입니다.

이 솔루션을 PHP로 구현해 보겠습니다: 2924. 챔피언 II 찾기

<?php /**
 * @param Integer $n
 * @param Integer[][] $edges
 * @return Integer
 */
function findChampion($n, $edges) {
    // Initialize in-degrees for all teams
    $inDegree = array_fill(0, $n, 0);

    // Calculate the in-degree for each team
    foreach ($edges as $edge) {
        $inDegree[$edge[1]]++;
    }

    // Find teams with in-degree 0
    $candidates = [];
    for ($i = 0; $i < $n; $i++) {
        if ($inDegree[$i] == 0) {
            $candidates[] = $i;
        }
    }

    // If exactly one team has in-degree 0, return it; otherwise, return -1
    return count($candidates) === 1 ? $candidates[0] : -1;
}

// Example 1
$n1 = 3;
$edges1 = [[0, 1], [1, 2]];
echo "Example 1 Output: " . findChampion($n1, $edges1) . PHP_EOL; // Output: 0

// Example 2
$n2 = 4;
$edges2 = [[0, 2], [1, 3], [1, 2]];
echo "Example 2 Output: " . findChampion($n2, $edges2) . PHP_EOL; // Output: -1
?>

설명:

1. 입력 구문 분석:

   • n은 팀 수입니다.
   • edge는 그래프의 방향이 있는 간선의 목록입니다.

2. 학번 초기화:

   • 0으로 초기화된 크기 n의 배열을 만듭니다.

3. 도수 계산:

   • 각 에지 [u, v]에 대해 v의 차수를 증가시킵니다(팀 v에는 들어오는 에지가 하나 더 있습니다).

4. 후보자 찾기:

   • inDegree 배열을 반복하고 indegree가 0인 인덱스를 수집합니다. 이 인덱스는 더 강한 팀이 없는 팀을 나타냅니다.

5. 챔피언 결정:

   • 정확히 한 팀이 0도를 기록했다면 그 팀이 유일한 챔피언이 됩니다.
   • 0차수가 여러 팀이거나 팀이 없는 경우 -1을 반환합니다.

예제 연습

예시 1:

• 입력: n = 3, 모서리 = [[0, 1], [1, 2]]
• 차수: [0, 1, 1]
• 차수가 0인 팀: [0]
• 출력: 0(팀 0이 고유 챔피언입니다.)

예시 2:

• 입력: n = 4, 모서리 = [[0, 2], [1, 3], [1, 2]]
• 차수: [0, 0, 2, 1]
• 차수가 0인 팀: [0, 1]
• 출력: -1(잠재 챔피언이 여러 명 있음)

복잡성 분석

1. 시간 복잡성:

   • 도 단위 계산: O(m), 여기서 m은 모서리 수입니다.
   • 팀 확인: O(n), 여기서 n은 팀 수
   • 합계: O(n·m).

2. 공간 복잡성:

   • inDegree 배열: O(n).

이 솔루션은 효율적이며 주어진 제약 조건 내에서 작동합니다.

연락처 링크

이 시리즈가 도움이 되었다면 GitHub에서 저장소에 별표를 표시하거나 즐겨찾는 소셜 네트워크에서 게시물을 공유해 보세요. 여러분의 지원은 저에게 큰 의미가 될 것입니다!

이렇게 더 유용한 콘텐츠를 원하시면 저를 팔로우해주세요.

• 링크드인
• 깃허브

위 내용은 챔피언 II 찾기의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!