UVALive 6187 并查集

題目連結：https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4198

題意：1~n個數，m個操作，！a b c的意思是第b個數減去第a個數等于c。

？a b的意思是問第b個數減去第a個數等于多少

代碼：

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
#define ll long long
const int maxn = 1e6+100;
ll dis[maxn];
int fa[maxn];
int n,m;
void init(){
    for(int i=1;i<=n;i++){
        dis[i] = 0;
        fa[i] = i;
    }
}
int find(int x){
    if(fa[x]!=x){
        int tmp = find(fa[x]);
        dis[x]+=dis[fa[x]];
        fa[x] = tmp;
    }
    return fa[x];
}
int main(){
    while(cin>>n>>m){
        if(n==0&&m==0)break;
        init();
        char op[2];
        int a,b,c;
        while(m--){
            scanf("%s",op);
            if(op[0] == '!'){
                scanf("%d%d%d",&a,&b,&c);
                int f1 = find(a);
                int f2 = find(b);
                if(f1!=f2){
                    fa[f2] = f1;
                    dis[f2] = dis[a] - dis[b] + c;
                }
            }
            else{
                scanf("%d%d",&a,&b);
                int f1 = find(a);
                int f2 = find(b);
                if(f1!=f2)cout<<"UNKNOWN"<<endl;
                else cout<<dis[b] - dis[a]<<endl;
            }
        }
    }
    return 0;
}