[SW3289] 서로소 집합

 SW Expert Academy - 서로소 집합 

문제 링크

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWBJKA6qr2oDFAWr&categoryId=AWBJKA6qr2oDFAWr&categoryType=CODE&problemTitle=%EC%84%9C%EB%A1%9C%EC%86%8C&orderBy=PASS_RATE&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1 

SW Expert Academy

 

문제 입출력

1
7 8
0 1 3
1 1 7
0 7 6
1 7 1
0 3 7
0 4 2
0 1 1
1 1 1

#1 001

 

문제 풀이

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


public class Solution {
	static String ans;
	static int T, N, M;
	static int[] parents;

	static StringBuilder sb = new StringBuilder();


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

		T = Integer.parseInt(br.readLine());
		for (int t = 1; t <= T; t++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			M = Integer.parseInt(st.nextToken());

			// 초기화
			parents = new int[N + 1];
			ans = "";

			makeSet();

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

				if (op == 0) union(a, b);
				else {
					int pA = findSet(a);
					int pB = findSet(b);

					if (pA == pB) ans += "1";
					else ans += "0";
				}

			}

			sb.append("#").append(t).append(" ").append(ans).append("\n");
		}

		System.out.println(sb.toString());

	} // end main


	private static void makeSet() {
		for (int i = 0; i < N; i++) parents[i] = i;
	} // end makeSet


	private static int findSet(int x) {
		if (x == parents[x]) return x;
		return parents[x] = findSet(parents[x]);
	} // end findSet


	private static boolean union(int x, int y) {
		int pX = findSet(x);
		int pY = findSet(y);

		if (pX == pY) return false;

		if (pX < pY) parents[pY] = pX;
		else parents[pX] = pY;

		return true;
	} // end union


	static class Edge {
		int f;
		int t;
		int w;


		public Edge(int f, int t, int w) {
			super();
			this.f = f;
			this.t = t;
			this.w = w;
		}


		@Override
		public String toString() {
			return "Edge [f=" + f + ", t=" + t + ", w=" + w + "]";
		}

	} // end Edge
}

• 서로소 집합 연산을 이용해서 풀 수 있다.

 

 

 

 

 

 

 

 

 

# SW 서로소 집합 # SWEA 서로소 집합

---