[백준 1778] Ubiquitous Religions - JAVA

 

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

 

분리 집합 문제

 

유니온-파인드로 분리 집합을 구성하고, 나올 수 있는 부모의 가짓수를 출력

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;
import java.util.StringTokenizer;

class Main {

  static int[] p;

  public static void main(String[] args) throws IOException {

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    int c = 1;
    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;
      }

      p = new int[N + 1];
      for (int i = 1; i <= N; i++) {
        p[i] = i;
      }

      for (int i = 0; i < M; i++) {
        st = new StringTokenizer(br.readLine());
        int a = Integer.parseInt(st.nextToken());
        int b = Integer.parseInt(st.nextToken());

        union(a, b);
      }

      Set<Integer> reli = new HashSet<>();

      int ans = 0;
      for (int i = 1; i <= N; i++) {

        int parent = find(i);
        if (!reli.contains(parent)) {
          reli.add(parent);
          ans++;
        }
      }

      System.out.println(String.format("Case %d: %d", c++, ans));
    }
  }

  static void union(int a, int b) {
    a = find(a);
    b = find(b);

    if (a > b) {
      p[b] = a;
    } else {
      p[a] = b;
    }
  }

  static int find(int a) {

    if (p[a] == a) {
      return a;
    }

    return p[a] = find(p[a]);
  }
}