Funcia
Lv.2graphunion-find

친구 네트워크의 무리 수

메모리 제한
256 MB
정확성 시간 제한
10000 ms
푼 사람
0
0

0번부터 n - 1번까지 n명의 사람이 있고, 처음에는 아무도 서로 친구가 아닙니다. links의 순서대로 친구 관계가 하나씩 맺어집니다. links[i] = [a, b]는 a와 b가 친구가 됐다는 뜻입니다.

친구의 친구도 같은 무리로 봅니다. 즉 친구 관계로 직접 또는 간접적으로 이어진 사람들이 한 무리입니다.

각 친구 관계가 맺어진 직후의 무리 수를 차례대로 배열에 담아 반환하세요.

입출력 예

nlinksresult
5[[0, 1], [1, 2], [3, 4], [0, 2], [2, 4]][4, 3, 2, 2, 1]
3[[1, 1], [0, 2]][3, 2]

입출력 예 설명

예 1 — 처음엔 5개 무리입니다. [0,1]로 4개, [1,2]로 3개({0,1,2}, {3}, {4}), [3,4]로 2개가 됩니다. [0,2]는 이미 같은 무리라 변화가 없고, [2,4]로 모두 하나가 됩니다.

예 2 — 자기 자신과의 관계 [1,1]은 무리 수를 바꾸지 않습니다.

효율성

이 문제에는 효율성 테스트가 있습니다. 제한 사항의 입력 크기를 보고 필요한 시간 복잡도를 직접 판단하세요.

함수 시그니처

solution(n: int, links: int[][]) → int[]

제한 사항

  • 1≤1 \le n ≤100,000\le 100{,}000
  • 1≤1 \le links.length ≤200,000\le 200{,}000
  • links[i] = [a, b], 0≤a,b<n0 \le a, b < n. a == b일 수도 있고, 같은 관계가 여러 번 나올 수도 있습니다.

기대 복잡도

시간
O((N + M) α(N))
공간
O(N)

입출력 예

nlinks기대 출력
5[[0,1],[1,2],[3,4],[0,2],[2,4]][4,3,2,2,1]
3[[1,1],[0,2]][3,2]

힌트

힌트

"두 사람이 같은 무리인가?"와 "두 무리를 합친다"만 빠르게 할 수 있으면 됩니다. 바로 유니온 파인드(서로소 집합)입니다.

  • parent[x]: 각 사람의 대표를 가리키는 배열. 처음엔 자기 자신.
  • find(x): 대표까지 따라 올라갑니다. 올라가면서 경로를 대표에 바로 붙이면(경로 압축) 다음부터 빨라집니다.
  • union(a, b): 두 대표가 다르면 한쪽을 다른 쪽 밑에 붙이고, 무리 수를 1 줄입니다.

무리 수는 n에서 시작해, 실제로 합쳐질 때만 1씩 줄이면 됩니다.

find를 재귀로 쓰면 합치는 순서에 따라 깊이가 커질 수 있습니다. 반복문으로 쓰거나, 작은 무리를 큰 무리 밑에 붙이세요(union by size).

복잡도 목표

관계가 추가될 때마다 BFS/DFS로 무리 수를 처음부터 다시 세면 O(M(N+M))O(M(N + M))이라 효율성 테스트에서 시간 초과가 납니다.

언어별 시간 제한

언어효율성 시간 제한
C (GCC, gnu17)200 ms추정
C++ (GCC, gnu++23)200 ms도출됨
Python 3.131000 ms도출됨
Java 251656 ms도출됨
Kotlin 2.4 (JVM)1400 ms추정
C# 14 (.NET 10)1400 ms추정

테스트 그룹

그룹배점테스트 수공개 범위
sample02입력·출력 공개
correctness409판정만
performance604판정만
에디터 불러오는 중…

아직 결과가 없습니다. 실행 또는 제출하세요.