Count the Number of Complete Components

MediumDepth-First SearchBreadth-First SearchUnion FindGraph

문제 설명

  • 정수 n이 주어집니다.
    • n개의 정점을 가진 무방향 그래프(Undirected Graph)가 있으며, 정점은 0부터 n-1까지 번호가 매겨져 있습니다.
  • edges 배열이 주어집니다.
    • edges[i] = [a, b]는 정점 a와 b사이에 무방향 간선이 존재한다는 것을 의미합니다.
  • 주어진 그래프에서 완전 연결된 요소(Complete Connected Component)의 개수를 반환하여야 합니다.
    • 연결 요소(Connected Component)란, 그래프의 부분 그래프 중에서 어떤 두 정점 사이든 경로가 존재하는 집합입니다.
    • 완전 연결된 요소(Complete Connected Component)란, 연결 요소 내부에 속한 모든 정점들이 직접 연결 된경우를 의미합니다.
      • 즉, k의 정점을 가진다면, 총 k * (k - 1) / 2 개의 간선이 존재해야 합니다.

문제 풀이

Union Find

이 문제는 Union-Find 자료구조를 활용하면 해결할 수 있습니다.

  1. Union-Find로 연결 요소 찾기
    • UnionFind 클래스를 사용하여 같은 컴포넌트에 속하는 노드를 그룹화합니다.
    • union(x, y): 두 노드를 같은 그룹으로 합침
    • find(x): 노드 x의 가장 위의 부모 노드를 찾음
  2. 각 연결 요소의 간선 개수 저장
    • edgeCounts를 사용하여 각 연결 요소의 간선 개수를 저장
    • edges의 루트 노드의 간선 개수를 증가시킨다.
  3. 완전 연결된 요소인지 확인
    • 모든 노드를 순회하며, 연결 요소(그룹)의 루트 노드인지 확인
    • 완전 그래프인지 확인 → (nodeSize * (nodeSize - 1)) / 2와 edgeCount가 같은지 비교
export function countCompleteComponents(n: number, edges: number[][]): number {
  // Union-Find를 사용한 각 노드를 연결 요소로 그룹화
  const unionFind = new UnionFind(n);
  for (const [a, b] of edges) {
    unionFind.union(a, b);
  }
 
  // 각 연결 요소에 대한 간선의 개수 저장
  const edgeCounts = new Map<number, number>();
  for (const [node] of edges) {
    const parentNode = unionFind.find(node);
    edgeCounts.set(parentNode, (edgeCounts.get(parentNode) ?? 0) + 1);
  }
 
  let answer = 0;
  for (let node = 0; node < n; node++) {
    const parentNode = unionFind.find(node);
    if (node !== parentNode) {
      continue;
    }
    // 각 연결 요소의 개수와 간선의 개수를 비교하여, 완전 연결 요소인지 여부를 확인
    const nodeSize = unionFind.sizes[node];
    const edgeCount = edgeCounts.get(node) ?? 0;
    const totalEdgeCount = (nodeSize * (nodeSize - 1)) / 2;
    if (edgeCount === totalEdgeCount) {
      answer += 1;
    }
  }
  return answer;
}
 
class UnionFind {
  public readonly sizes: number[];
  private readonly parents: number[];
 
  constructor(n: number) {
    this.sizes = new Array<number>(n).fill(1);
    this.parents = Array.from({ length: n }, (_, i) => i);
  }
 
  find(x: number): number {
    if (this.parents[x] !== x) {
      this.parents[x] = this.find(this.parents[x]);
    }
    return this.parents[x];
  }
 
  union(x: number, y: number): void {
    const parentX = this.find(x);
    const parentY = this.find(y);
    if (parentX === parentY) return;
 
    if (this.sizes[parentX] > this.sizes[parentY]) {
      this.parents[parentY] = parentX;
      this.sizes[parentX] += this.sizes[parentY];
    } else {
      this.parents[parentX] = parentY;
      this.sizes[parentY] += this.sizes[parentX];
    }
  }
}

복잡도

  • 시간 복잡도: O(n+m)O(n + m)
    • mm: 모든 간선의 개수
  • 공간 복잡도: O(n)O(n)
LeetCode
Count the Number of Complete Components
https://leetcode.com/problems/count-the-number-of-complete-components