[BOJ] 20040.사이클 게임(Union,Find).java

#. Problem

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

* The copyright in this matter is in BOJ

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

간선을 하나씩 그어보면서

그래프에 사이클이 형성되는지 확인하는 문제이다.

사이클이 형성되는지 확인하기 위해서는 

MST Kruskal 알고리즘에도 활용되는 Union, Find 를 활용할 수 있다.

#. Code

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer;   public class BOJ20040 {       static int N, M, res, parents[];          public static void main(String[] args) throws IOException {           BufferedReader br = new BufferedReader(new InputStreamReader(System.in));         StringTokenizer st = new StringTokenizer(br.readLine());                  N = Integer.parseInt(st.nextToken());         M = Integer.parseInt(st.nextToken());           parents = new int[N];         for (int i = 0; i < N; i++) {             parents[i] = i;         }                  for (int i = 1; i <= M; i++) {             st = new StringTokenizer(br.readLine());             int a = Integer.parseInt(st.nextToken());             int b = Integer.parseInt(st.nextToken());             // 사이클이 형성되는지 확인             if(!union(a, b)) {                 res = i;                 break;             }         }                  System.out.println(res);     }       private static boolean union(int a, int b) {         int aRoot = find(a); // a의 root 노드         int bRoot = find(b); // b의 root 노드         // a와 b의 root 노드가 같다면 사이클 형성         if(aRoot == bRoot) return false;         parents[bRoot] = aRoot;         return true;     }       private static int find(int n) {         if(n == parents[n]) return n;         return parents[n] = find(parents[n]);     }   }   Colored by Color Scripter

cs