• 문제

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

• Union Find 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static int[] parent;
    static long[] weight;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        while(true){
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");

            int n = Integer.parseInt(st.nextToken());
            int m = Integer.parseInt(st.nextToken());

            if(n == 0 && m == 0) break;

            parent = new int[n + 1];
            for (int i = 1; i <= n; i++) {
                parent[i] = i;
            }
            weight = new long[n + 1];

            String work;
            int a, b, w;

            for (int i = 0; i < m; i++) {
                st = new StringTokenizer(br.readLine());
                work = st.nextToken();

                if (work.equals("!")) {
                    a = Integer.parseInt(st.nextToken());
                    b = Integer.parseInt(st.nextToken());
                    w = Integer.parseInt(st.nextToken());

                    union(a, b, w);
                }
                else {
                    a = Integer.parseInt(st.nextToken());
                    b = Integer.parseInt(st.nextToken());

                    if (find(a) != find(b)) {
                        sb.append("UNKNOWN\\n");
                    }
                    else {
                        sb.append((weight[b] - weight[a]) + "\\n");
                    }
                }
            }
        }

        System.out.println(sb);
    }

    public static int find(int a){
        if(parent[a] == a) return a;

        int tmp = find(parent[a]);
        weight[a] += weight[parent[a]];
        return parent[a] = tmp;
    }

    public static void union(int a, int b, long w){
        int parent_a = find(a);
        int parent_b = find(b);

        if(parent_a == parent_b) return;

        weight[parent_b] = weight[parent_a] + weight[a] - weight[b] + w;
        parent[parent_a] = parent_b;
    }

}

• 오프라인 쿼리 풀이

import java.awt.*;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
    static int[] parent;
    static long[] weight;
    static boolean[] check;
    static ArrayList<Point>[] nodelist;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        while(true){
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");

            int n = Integer.parseInt(st.nextToken());
            int m = Integer.parseInt(st.nextToken());

            if(n == 0 && m == 0) break;

            parent = new int[n+1];
            weight = new long[n+1];

            for(int i = 0; i<n+1; i++){
                parent[i] = i;
            }

            int a,b,w;

            nodelist = new ArrayList[n+1];
            ArrayList<Point> query = new ArrayList<>();
            boolean[] possibility = new boolean[m+1];

            for(int i = 0; i<n+1; i++){
                nodelist[i] = new ArrayList<>();
            }

            for(int i = 0; i<m; i++){
                st = new StringTokenizer(br.readLine(), " ");

                char work = st.nextToken().charAt(0);

                if(work == '!'){
                    a = Integer.parseInt(st.nextToken());
                    b = Integer.parseInt(st.nextToken());
                    w = Integer.parseInt(st.nextToken());

                    if(union(a,b)){
                        nodelist[a].add(new Point(b,w));
                        nodelist[b].add(new Point(a,-w));
                    }
                }
                else{
                    a = Integer.parseInt(st.nextToken());
                    b = Integer.parseInt(st.nextToken());
                    query.add(new Point(a,b));
                    if(find(a) != find(b)){
                        possibility[query.size()-1] = true;
                    }
                }
            }

            check = new boolean[n+1];

            for(int i = 1; i<n+1; i++){
                if(!check[i]) dfs(i,0);
            }
            for(int i = 0; i<query.size(); i++){
                a = query.get(i).x;
                b = query.get(i).y;
                if(possibility[i]) sb.append("UNKNOWN\\n");
                else sb.append((weight[b]- weight[a]) + "\\n");

            }

        }

        System.out.println(sb);
    }

    public static int find(int a){
        if(parent[a] == a) return a;

        int tmp = find(parent[a]);
        weight[a] += weight[parent[a]];
        return parent[a] = tmp;
    }

    public static boolean union(int a, int b){
        int parent_a = find(a);
        int parent_b = find(b);

        if(parent_a == parent_b) return false;
        parent[parent_a] = parent_b;
        return true;
    }

    public static void dfs(int v, int w){
        check[v] = true;
        weight[v] = w;
        for(Point nxt : nodelist[v]){
            int b = nxt.x;
            if(check[b]) continue;
            check[b] = true;
            dfs(b, w + nxt.y);
        }
    }

}