2606번: 바이러스

https://www.acmicpc.net/problem/2606


$O(nα(n))$

union-find 자료구조를 이용해 1번과 같은 집합에 속한 컴퓨터 수를 구한다.

#include<cstdio>
int n, m, r, p[101];
int f(int x) { return x == p[x] ? x : p[x] = f(p[x]); }
int main() {
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++) p[i] = i;
    for (int i = 0, x, y; i < m; i++) scanf("%d %d", &x, &y), p[f(x)] = f(y);
    for (int i = 2; i <= n; i++) r += f(1) == f(i);
    printf("%d", r);
    return 0;
}