[BOJ 3830] 교수님은 기다리지 않는다

문제 출처 : https://www.acmicpc.net/problem/3830

 

풀이 :

 

disjoint-set (Union-Find) 문제입니다.

find를 할때마다 속도를 개선시켜주기 위해 부모를 루트로 지정해주고 무거운 정도를 루트 부터 1촌 부모까지의 차이로 저장해주고, Union 연산을 할때 점화식을 세울때 주의해서 세워주시면 됩니다.

 

#include<stdio.h>
typedef long long ll;
 
int n, m, a, b, c, parent[100001],cnt;
ll wei[100001];
char ch;
 
int find(int a) {
    if (a == parent[a])return a;
    int prev = find(parent[a]);
    wei[a] += wei[parent[a]];
    return parent[a] = prev;
}
 
int main() {
    while (1) {
        scanf("%d %d", &n, &m);
        if (n == 0 && m == 0)return 0;
        cnt++;
        for (int i = 1; i <= n; i++) {
            parent[i] = i;
            wei[i] = 0;
        }
        while (m--) {
            scanf(" %c", &ch);
            if (ch == '!') {
                scanf("%d %d %d", &a, &b, &c);
                int l = find(a);
                int r = find(b);
                if (l != r) {
                    parent[l] = r;
                    wei[l] = wei[b] - wei[a] + c;
                }
            }
            else {
                scanf("%d %d", &a, &b);
                int l = find(a);
                int r = find(b);
                if (l != r) {
                    printf("UNKNOWN\n");
                    continue;
                }
                else printf("%lld\n", wei[a] - wei[b]);
            }
        }
    }
}