3830번-교수님은 기다리지 않는다.

문제

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

3830번: 교수님은 기다리지 않는다

---

접근방법

1) 접근 사고

 

2) 시간 복잡도

 

3) 배운 점

 

4) PS

---

정답 코드

#include<bits/stdc++.h>
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define pii pair<int,int>
#define mp(X,Y) make_pair(X,Y)
#define mt(X,Y) make_tuple(X,Y)
#define mtt(X,Y,Z) make_tuple(X,Y,Z)
#define ll long long
#define sz(v) (int)(v).size()
 
using namespace std;
const int MAX = 100001;
int n, m;
int parent[MAX];
ll dist[MAX];
 
int find(int c)
{
    if(parent[c] == c)
        return c;
    int idx = find(parent[c]);
    //현재 트리 형식으로 이루어져있으니 find를 통해 차이 값 들을 갱신 시켜주는 작업
    dist[c] += dist[parent[c]];
    return parent[c] = idx;
}
 
void merge(int a, int b, int diff)
{
    int pa = find(a);
    int pb = find(b);
 
    if(pa == pb)
        return;
 
    //차이값 계산
    dist[pb] = dist[a] - dist[b] + diff;
    parent[pb] = pa;
    return;
}
int main(void)
{
    fastio;
    while(1)
    {
        cin >> n >> m;
        if(n == 0 && m == 0)
            break;
 
        for(int i = 1; i <= n; i++)
            parent[i] = i;
        fill(dist, dist + MAX, 0);
        for(int i = 0; i < m; i++)
        {
            char cmd;
            cin >> cmd;
            if(cmd == '!')
            {
                int a, b, c;
                cin >> a >> b >> c;
                merge(a, b, c);
            }
            else if(cmd == '?')
            {
                int a, b;
                cin >> a >> b;
                if(find(a) != find(b))
                    cout << "UNKNOWN" <<"\n";
                else
                    cout << dist[b] - dist[a] << "\n";
            }
        }
    }
}