찾다

집 >백엔드 개발 >PHP 튜토리얼 >노드를 최대 그룹 수로 나눕니다

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

Linda Hamilton
Linda Hamilton원래의
2025-01-30 10:03:10628검색
<..> 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. "문제, "노드를 최대 그룹 수로 나눕니다. "는 방정되지 않은 그래프의 노드가 나눌 수있는 최대 그룹 수를 결정하는 것과 관련이 있습니다.
    2. 각 노드는 정확히 하나의 그룹에 속합니다.
      3. 인접한 노드는 지수가 정확히 1만큼 다른 그룹으로 이루어집니다. 그래프가 당파트가 아닌 경우 그룹화가 불가능하며 함수는 -1.
    키 포인트

    그래프 속성 :

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

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

    전처리 :

    인접성 목록을 사용하여 그래프를 나타냅니다 노조 찾기를 사용하여 연결된 구성 요소를 식별하십시오
    • 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. 시간 복잡성
              • 그래프 구조 :
            2. o (e)
            3. , 여기서

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

          LinkedIn

          github

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

php edge Integer Array if count for while union using class Length finally number function this position input github Other
성명：
본 글의 내용은 네티즌들의 자발적인 기여로 작성되었으며, 저작권은 원저작자에게 있습니다. 본 사이트는 이에 상응하는 법적 책임을 지지 않습니다. 표절이나 침해가 의심되는 콘텐츠를 발견한 경우 admin@php.cn으로 문의하세요.
이전 기사：. 중복 연결다음 기사：. 중복 연결

관련 기사

더보기