[백준]교수님은 기다리지 않는다(3830)

문제 링크 : [백준]교수님은 기다리지 않는다(3830)

문제 설명

N개의 샘플이 있고, M번 두 샘플간의 무게 관계가 M번 주어지거나, 두 샘플간의 무게 관계를 조회하는 쿼리가 주어집니다.
조회 쿼리가 주어지면, 그동안 주어진 샘플간의 관계를 이용하여 무게 관계를 유추할 수 있는지, 있다면 차이가 얼마나 나는지 출력하세요.

입력

N(샘플의 갯수, 1 <= N <= 100,000)
M(쿼리의 수, 1 <= M <= 100,000)
M개의 줄에 걸쳐 아래와 같은 형식으로 입력이 주어집니다.
! a b w(b가 a보다 w만큼 무겁습니다.)
? a b(b가 a보다 얼마나 무거운지 출력합니다.)

2 2
! 1 2 1
? 1 2
2 2
! 1 2 1
? 2 1
4 7
! 1 2 100
? 2 3
! 2 3 100
? 2 3
? 1 3
! 4 3 150
? 4 1
0 0

출력

1
-1
UNKNOWN
100
200
-50

카테고리

#DisjointSet

시간 복잡도 상한

O(NlogM) 혹은 O(MlogN)

해결 방법

1. 두 샘플들간의 관계들이 서로 이어지는 경우(a < b, b <c라면 a < c)가 아니라면 샘플간의 관계를 유추 할 수 없습니다.
2. 이런 관계는 DisjointSet으로 그룹핑하여 같은 그룹으로 묶였는지로 판단을 하면 가능합니다.
3. 또한 DisjointSet으로 그룹 정보를 저장할 때, 샘플간의 관계도 저장하면 원하는 자료를 저장 할 수 있습니다.
4. 두 샘플의 관계를 저장 할 때, 한 지점을 그룹의 대표로 설정하고, 같은 그룹은 그 지점과의 차이를 저장하게 합니다.
5. 조회를 할 때는, 두 샘플이 그룹의 대표와의 차이를 가지고 계산합니다.

시간복잡도

O(M)

코드

#include<iostream>
#define l long long
using namespace std;
l g[100001],d;
int n,m,b,c,e[100001];
char a;
int f(int a){
    if(e[a]==a)return a;
    int t=e[a];
    e[a]=f(e[a]);
    g[a]+=g[t];
    return e[a];
}
void u(int a,int b,l v){
    if(a>b){
        int t=a;
        a=b,b=t;
        v=-v;
    }
    f(a);f(b);
    l x=g[b],y=g[a];
    a=f(a);b=f(b);
    e[b]=a;g[b]=v+y-x;
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    while(1){
        cin>>n>>m;
        if(!n)break;
        for(b=1;b<=n;b++)e[b]=b,g[b]=0;
        while(m--){
            cin>>a>>b>>c;
            if(a=='!'){
                cin>>d;
                u(b,c,d);
            }else{
                if(f(b)==f(c))cout<<g[c]-g[b]<<'\n';
                else cout<<"UNKNOWN\n";
            }
        }
    }
}