[SW Expert Academy Java]3289 서로소 집합

문제

---

SW Expert Academy

SW Expert Academy

풀이방법

---

go라는 변수를 만들어 합집합인지, 두 원소가 같은 집합에 포함되어 있는지 확인하는 연산인지를 구분한다.

합집합은 make의 함수를 사용한다. 모든 노드가 자신을 부모로하는(대표자) 집합으로 만든다.

 

go가 1이라면, find함수를 사용해 각각의 대표자(부모)를 찾아주고, 부모가 같다면(같은 집합에 포함되어있다면 ) 1을, 아니면 0을 출력해준다.

 

make함수와 find함수가 잘 이해가 안된다면 아래의 글을 읽어보도록 하자!

 

서로소 집합 만들기 (tistory.com)

서로소 집합 만들기

코드

---

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



public class Solution {
	static class Edge{
		int go, from, to;
		
		public Edge(int go, int from, int to) {
			this.go = go;
			this.from = from;
			this.to = to;
		}
	}

	static int n,m;
    static int[] parents;
    static Edge[] edgeList;

    static void make() {
        parents = new int[n+1];
        for(int i=0; i<=n; i++) { //모든 노드가 자신을 부모로하는(대표자) 집합으로 만듦
            parents[i]=i;

        }
    }

    static int find(int a) { //a의 대표자 찾기
        if(parents[a]==a) return a;
        return parents[a]=find(parents[a]); 
    }

    static boolean union(int a, int b) { //리턴값: true ==> union성공
        int aRoot = find(a);
        int bRoot = find(b);

        if(aRoot == bRoot) return false;

        parents[bRoot] = aRoot;
        return true;
    }
    
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int T=Integer.parseInt(st.nextToken());
		for(int test=0; test<T; test++) {
			st = new StringTokenizer(br.readLine());
			
			n=Integer.parseInt(st.nextToken());
			m=Integer.parseInt(st.nextToken());
			
			edgeList = new Edge[m];
			make();

			System.out.printf("#%d ",test+1);
			for(int i=0; i<m; i++) {
				st = new StringTokenizer(br.readLine());
				int go=Integer.parseInt(st.nextToken());
				int a=Integer.parseInt(st.nextToken());
			    int b=Integer.parseInt(st.nextToken());
			    if(go==0) {
			    	union(a,b);
			    }
			    if(go==1) {
			    	if(find(a) == find(b)) {
			    		System.out.print(1);
			    	}
			    	else {
			    		System.out.print(0);
			    	}
			    }
//				edgeList[i] = new Edge(go,a,b);

			}
			System.out.println();

	}

	}
	
}