백준 7511 (소셜 네트워킹 어플리케이션) - java

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

 

문제

어렸을때부터 컴퓨터 프로그래밍에 엄청난 소질을 보인 상근이는 항상 소셜 네트워킹 웹사이트를 만들고 싶어 했다. 상근이는 페이스북을 벤치마킹하기 위해 지난 3년간 열심히 사용을 했고, 이제 페이스북의 단점을 보완한 새 소셜 네트워킹 웹 2.0 어플리케이션을 만들려고 한다.

사람들은 소셜 네트워킹 어플리케이션에 가입을 한 다음, 현실에서 아는 사람을 친구로 추가하기 시작한다. 이러한 친구 관계 정보를 이용해 친구 관계 그래프를 그릴 수 있다.

소셜 네트워킹 어플리케이션에서 가장 중요한 기능은 한 사람이 다른 사람의 페이지를 방문했을 때, 친구 관계 그래프에서 두 사람 사이의 경로를 보여주는 기능이다. 경로가 없는 경우에는 보여주지 않는다.

상근이의 서비스는 매우 유명해졌고, 위의 기능은 사람들이 점점 많아질수록 경로를 구하는 시간이 매우 느려지게 되었다. 그 이유는 두 사람 사이의 경로가 없는 경우에 경로를 찾기 위해 너무 오랜시간 그래프를 탐색하기 때문이었다. 따라서, 상근이는 두 사람 사이의 경로가 존재하는지 안 하는지를 미리 구해보려고 한다.

유저의 수와 각 유저의 친구 관계가 입력으로 주어진다. 이때, 주어지는 두 사람이 친구 관계 그래프상에서 경로가 존재하는지 안 하는지를 구하는 프로그램을 작성하시오.

 

유형 : Union - Find

 

전체 코드

import java.util.*;
import java.io.*;

public class Main {

    static int t,n,m,k;
    static int[] root = new int[1000001];

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        StringBuilder sb = new StringBuilder();
        t = Integer.parseInt(st.nextToken());

        for(int a = 1 ; a <= t ; a++){
            st = new StringTokenizer(br.readLine()," ");
            n = Integer.parseInt(st.nextToken());

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

            st = new StringTokenizer(br.readLine()," ");
            m = Integer.parseInt(st.nextToken());

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

                if(find(v1) != find(v2)) {
                    union(v1,v2);
                }
            }

            st = new StringTokenizer(br.readLine()," ");
            k = Integer.parseInt(st.nextToken());

            sb.append("Scenario "+a+":\n");

            for(int i = 0 ; i < k ; i++){
                st = new StringTokenizer(br.readLine()," ");
                int v1 = Integer.parseInt(st.nextToken());
                int v2 = Integer.parseInt(st.nextToken());

                if(find(v1) == find(v2)) {
                    sb.append("1\n");
                }else{
                    sb.append("0\n");
                }
            }sb.append("\n");
        }

        System.out.println(sb);
        br.close();
    }

    static int find(int x) {
        if(x == root[x])
            return root[x];

        return root[x] = find(root[x]);
    }

    static void union(int x,int y) {
        x = find(x);
        y = find(y);

        if(x < y)
            root[y] = x;
        else
            root[x] = y;
    }
}