노드를 최대 그룹 수로 나눕니다

<..> 2493. 노드를 최대 그룹 로 나눕니다 난이도 :

하드 주제 : 폭이 먼저 검색, Union Find, Graph 당신은

방향 그래프의 노드 수를 나타내는 양의 정수 n이 주어집니다. 노드는 1에서 n 당신은 또한 2D 정수 배열 모서리가 주어지며, 여기서 가장자리 [i] = [a

i , b i

]는 a

bidirectional 가 있음을 나타냅니다. 노드 사이의 가장자리 a i 및 b

i

. 주어진 그래프가 연결이 끊어 질 수 있다는 통지 그래프의 노드를 m 그룹으로 나눕니다 () :

그래프의 각 노드는 정확히 하나의 그룹에 속합니다.

a 에 가장자리에 연결된 그래프의 모든 노드 쌍에 대해 a i _{가 그룹에 속하는 경우 인덱스 x와 b} i 는 index y를 가진 그룹에 속합니다. | y -x | = 1. <.> _{return 노드를 나눌 수있는 최대 그룹 수 (즉, 최대 m). 주어진 조건으로 노드를 그룹화하는 것이 불가능한 경우 -1을 반환하십시오. 예 1 :} 입력 : n = 6, 가장자리 = [[1,2], [1,4], [1,5], [2,6], [2,3], [4,6] ]

출력 :

4 <:> 설명 : 이미지에 표시된대로 우리 : 첫 번째 그룹에 노드 5를 추가하십시오 두 번째 그룹에 노드 1을 추가하십시오 노드 2와 4를 세 번째 그룹에 추가하십시오 네 번째 그룹에 노드 3과 6을 추가하십시오 우리는 모든 모서리가 만족되는 것을 볼 수 있습니다.

우리가 다섯 번째 그룹을 만들고 세 번째 또는 네 번째 그룹에서 노드를 이동하면 최소한 가장자리에 만족하지 못한다는 것을 알 수 있습니다.

.
• _{예제 2 :} 입력 : n = 3, 가장자리 = [[1,2], [2,3], [3,1]] _{출력 : -1} <:> 설명 : _{우리가 첫 번째 그룹에 노드 1을, 노드 2에 두 번째 그룹에 노드 1을, 3 그룹에 노드 3을 추가하면 첫 번째 두 모서리를 만족 시키면 세 번째 모서리가 만족되지 않을 것임을 알 수 있습니다. .} 그룹화가 불가능하다는 것을 알 수 있습니다

제약 조건 : 1 & lt; = n & lt; = 500 1 & lt; = edges.length & lt; = 10 4

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

1 & lt; = a i , b

i

& lt; = n

a

i i 정점 사이에는 최대 하나의 가장자리가 있습니다. 힌트 :
• 그래프가 양당이 아닌 경우 노드를 그룹화 할 수 없습니다. 각 연결된 구성 요소의 문제를 독립적으로 해결할 수 있으며 최종 답변은 각 구성 요소의 최대 그룹 수의 합입니다. 마지막으로, 각 연결된 구성 요소에 대한 문제를 해결하기 위해, 일부 노드 v의 경우 위치가 가장 왼쪽 그룹에있는 위치를 고정하면 다른 모든 노드의 위치를 ​​평가할 수도 있음을 알 수 있습니다. 그 위치는 노드에서 루팅 한 후 BFS 트리의 노드 깊이입니다.
  1. 솔루션 :
  "문제, "노드를 최대 그룹 수로 나눕니다. "는 방정되지 않은 그래프의 노드가 나눌 수있는 최대 그룹 수를 결정하는 것과 관련이 있습니다.
  2. 각 노드는 정확히 하나의 그룹에 속합니다.
  인접한 노드는 지수가 정확히 1만큼 다른 그룹으로 이루어집니다. 그래프가 당파트가 아닌 경우 그룹화가 불가능하며 함수는 -1.
  키 포인트
  그래프 속성 :

  그래프가 분리 될 수 있습니다 유효성 검사 : 각 연결된 구성 요소의 경우 양파장인지 확인하십시오. 그렇지 않은 경우 -1

  분파 적 성질 : 솔루션은 BFS와 관련하여 양당 성을 검증합니다
  <:> Union-find :
  1. 연결된 구성 요소를 효율적으로 그룹화하는 데 유용합니다
  접근

  전처리 :

  인접성 목록을 사용하여 그래프를 나타냅니다 노조 찾기를 사용하여 연결된 구성 요소를 식별하십시오
  • BFS 이중 문자를 검증하기위한 BFS :
  각 연결된 구성 요소의 경우 BFS를 사용하여 2 분파인지 확인하십시오. 이당이 아닌 경우 -1
  • 그룹 계산 :
  • 각 연결된 구성 요소의 경우 BFS를 사용하여 최대 그룹 수를 나타냅니다.
  결과를 ​​결합하십시오 :
  • 모든이 분파 성분의 최대 그룹 수를 합계합니다

  계획

  그래프를 인접성 목록으로 구성하십시오 연결된 구성 요소를 그룹화하기 위해 Union 찾기를 사용하십시오 그래프의 각 노드에 대해
  BFS를 사용하여 그래프가 양당인지 확인하고 해당 구성 요소의 최대 깊이를 계산합니다.

  1. 결과적으로 모든 구성 요소의 깊이의 합을 반환하십시오. 구성 요소가 당파트가 아닌 경우 -1 PHP 에서이 솔루션을 구현합시다 : 2493. 노드를 최대 그룹의 그룹

     로 나눕니다

     • <?php /**
        * @param Integer $n
        * @param Integer[][] $edges
        * @return Integer
        */
       function magnificentSets($n, $edges) {
           ...
           ...
           ...
           /**
            * go to ./solution.php
            */
       }
       
       /**
        * @param $graph
        * @param $u
        * @return int
        */
       private function bfs($graph, $u) {
           ...
           ...
           ...
           /**
            * go to ./solution.php
            */
       }
       
       class UnionFind {
           /**
            * @var array
            */
           private $id;
           /**
            * @var array
            */
           private $rank;
       
           /**
            * @param $n
            */
           public function __construct($n) {
              ...
              ...
              ...
              /**
               * go to ./solution.php
               */
           }
       
           /**
            * @param $u
            * @param $v
            * @return void
            */
           public function unionByRank($u, $v) {
              ...
              ...
              ...
              /**
               * go to ./solution.php
               */
           }
       
           /**
            * @param $u
            * @return mixed
            */
           public function find($u) {
              ...
              ...
              ...
              /**
               * go to ./solution.php
               */
           }
       }
       
       
       // Example usage:
       $n = 6;
       $edges = [[1,2], [1,4], [1,5], [2,6], [2,3], [4,6]];
       echo maxGroups($n, $edges); // Output: 4
       
       $n = 3;
       $edges = [[1,2], [2,3], [3,1]];
       echo maxGroups($n, $edges); // Output: -1
       ?>
       

       설명:

       1. 노조 찾기 클래스 Union-Find (Disjoint Set Union) 구조 그룹 노드를 연결된 구성 요소로 그룹화하고 두 가지 주요 작업을 수행합니다.

       찾기 :
       노드의 연결된 구성 요소의 루트를 식별하십시오
       • Union : 는 순위를 기준으로 두 개의 연결된 구성 요소를 병합합니다
       • 2. 이중 파파트 점검 및 깊이 계산을위한 BFS
       분파 유효성 검증 : BFS를 사용하여 "색상"을 노드에 번갈아 가며 할당하십시오. 인접한 노드가 동일한 색상을 공유하는 경우 그래프는 당파트가 아닙니다.

       깊이 계산 : 그룹의 최대 수를 결정하기 위해 BFS 트리의 깊이를 측정합니다.

       • 3. 결과를 결합하십시오 각 연결된 구성 요소의 최대 깊이를 계산합니다 결과를 ​​결정하려면 모든 구성 요소의 깊이를 추가하십시오.
       • 예제 연습 예 1
       입력 :
       단계 :
       인접성 목록 구성 :
       연결된 구성 요소에서 BFS 사용 :
       <:> 구성 요소 1 : 이분물. 최대 깊이 = 4.

       모든 구성 요소에서 합의 : 4. 출력 : 4

       예제 2 입력 :

       
       단계 :

       인접성 목록 구성 :

       $n = 6;  
       $edges = [[1,2], [1,4], [1,5], [2,6], [2,3], [4,6]];
       

       BFS 사용 :
       1. <:> 구성 요소 1 : 이분이 아님.

          1 -> [2, 4, 5]
          2 -> [1, 3, 6]
          3 -> [2]
          4 -> [1, 6]
          5 -> [1]
          6 -> [2, 4]
       

       출력 : -1
       1. 시간 복잡성
          그래프 구조 :
       o (e)
       , 여기서

       e

       는 가장자리의 수입니다.

       <: :> Union-find :

       o (α (n))

       
       . 경로 압축으로 인해 거의 일정)

       <:> bfs :

       $n = 3;  
       $edges = [[1,2], [2,3], [3,1]];
       

       o (v e)

       . 전반적인 복잡성 :
       1. o (n e)

          1 -> [2, 3]
          2 -> [1, 3]
          3 -> [1, 2]
       

       예제의 출력
       1. • 이 접근법은 양이파생 검사 및 깊이 계산을 위해 BFS를 활용하여 Union-Find를 활용하여 구성 요소 관리를 단순화하여 그룹화 문제를 효율적으로 처리합니다. 이 솔루션은 연결된 그래프와 연결이 끊긴 그래프를 모두 처리합니다
          연락처 링크
          이 시리즈가 도움이된다면 리포지토리 Github에 별을 주거나 좋아하는 소셜 네트워크에서 게시물을 공유하는 것이 무엇입니까? 당신의 지원은 나에게 큰 의미가 있습니다!
       이와 같은 유용한 콘텐츠를 원한다면 언제든지 나를 따르십시오 :

       LinkedIn

       github

위 내용은 노드를 최대 그룹 수로 나눕니다의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!