1717. 집합의 표현

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

1717번: 집합의 표현

Union-Find를 쓰면 간단히 해결된다.

<JAVA>

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

class Main {
	static int N, M;
	static int p[] = new int[1000001];

	static int find(int n) {
		if (p[n] == n)
			return n;
		else
			return p[n] = find(p[n]);
	}

	static void union(int x, int y) {
		x = find(x);
		y = find(y);
		if (x == y)
			return;
		p[x] = y;
	}

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		N = Integer.parseInt(st.nextToken(" "));
		M = Integer.parseInt(st.nextToken(" "));
		for (int i = 0; i <= N; i++) {
			p[i] = i;
		}
		for (int i = 0; i < M; ++i) {
			st = new StringTokenizer(br.readLine(), " ");
			switch (Integer.parseInt(st.nextToken(" "))) {
			case 0:
				union(Integer.parseInt(st.nextToken(" ")), Integer.parseInt(st.nextToken(" ")));
				break;
			case 1:
				if (find(Integer.parseInt(st.nextToken(" "))) == find(Integer.parseInt(st.nextToken(" ")))) {
					System.out.println("YES");
				} else {
					System.out.println("NO");
				}
				break;
			}
		}
	}
}

<C++>

#include<iostream>
using namespace std;
int N, M;
int map[1000001];
int find(int n) {
	if (map[n] == n)
		return n;
	else
		return map[n] = find(map[n]);
}
void _union(int x, int y) {
	x = find(x);
	y = find(y);
	if (x == y)
		return;
	map[x] = y;
}

int main() {
	cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(false);
	int temp, p, q;
	cin >> N >> M;
	for (int i = 0; i <= N; i++) {
		map[i] = i;
	}
	for (int i = 0; i < M; ++i) {
		cin >> temp >> p >> q;
		switch (temp) {
		case 0:
			_union(p, q);
			break;
		case 1:
			if (find(p) == find(q)) {
				cout << "YES\n";
			}
			else {
				cout << "NO\n";
			}
			break;
		}
	}
	return 0;
}