챔피언 II 찾기

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

해결책:

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

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

  
  
  설명:




입력 구문 분석:



n은 팀 수입니다.

edge는 그래프의 방향이 있는 간선의 목록입니다.



학번 초기화:


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



도수 계산:


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



후보자 찾기:


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



챔피언 결정:


정확히 한 팀이 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(잠재 챔피언이 여러 명 있음)



  
  
  복잡성 분석




시간 복잡성:


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



공간 복잡성:



inDegree 배열: O(n).




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

연락처 링크

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

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

링크드인
깃허브