Union Find (disjoint set)

코드

#include <stdio.h>
#include <algorithm>

using namespace std;

typedef long long int lld;

int p[10002], visit[10002];

int find(int n) {
    if (p[n] < 0) return n;
    return p[n] = find(p[n]);
}

void merge(int a, int b) {
    a = find(a);
    b = find(b);
    if (a == b) return;
    int t = max(p[a], p[b]);
    p[a] = b;
    p[b] = t;
}

int main()
{
    int n, m, k, i, a, b;
    lld sum = 0;

    scanf("%d%d%d", &n, &m, &k);
    for (i = 1; i <= n; i++) {
        scanf("%d", &p[i]);
        p[i] = -p[i];
    }
    while (m--) {
        scanf("%d%d", &a, &b);
        merge(a, b);
    }
    for (i = 1; i <= n; i++) {
        int t = find(i);
        if (visit[t] == 0) {
            visit[t] = 1;
            sum += -p[t];
        }
    }

    if (sum > k)
        printf("Oh no");
    else
        printf("%lld", sum);

    return 0;
}

16562 친구비에 대한 풀이

정리

  • find
    • 최악 시간복잡도는 O(MN), 그러나 평상시에 O(Mlog*N) 이며, log* 는 아크만함수로 N이 아무리커져도 상수에 수렴한다. 즉 O(M) 의 시간복잡도를 가지는 것과 같다
    • 부모가 -1인 노드를 찾을 때 까지 재귀호출하고, 그 부모의 값을 자신의 부모로 저장한 뒤 반환한다.
  • union
    • 둘의 부모를 찾은 뒤, 부모가 다르면 한쪽의 자식으로 넣는다.
  • 추가적인 정보를 넣을 수 있다
    • 예를들면 집합의 크기와 같은 속성을 union-find 를 통해서 저장할 수 있다.
    • 루트의 부모는 음수이므로, 집합의 크기를 -n 으로 저장할 수 있고, 집합의 크기가 큰 쪽이 부모가 되는 등의 작업을 구현 할 수 있다. (여러 문제를 살펴봐야 한다)

관련 문제

  • 1717 집합의표현

  • 1976 여행가자

  • 16562 친구비

  • 4195 친구네트워크

  • 9938 방청소

  • 10775 공항

  • 3780 Coporative Network ★

참고 자료

results matching ""

    No results matching ""