[6일차] 그래프1 A - 1717: 집합의 표현

골드 Ⅳ

 

#include <iostream>
using namespace std;

int parent[1000001];

int find(int node) {
	if (parent[node] == node) return node;
	return parent[node] = find(parent[node]);
}

void uni(int node1, int node2) {
	parent[find(node1)] = find(node2);
}

int n, m;
int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++) parent[i] = i;

	int cmd, a, b;
	while (m--) {
		scanf("%d%d%d", &cmd, &a, &b);

		if (cmd == 0) uni(a, b);
		else {
			if (find(a) == find(b)) printf("YES\n");
			else printf("NO\n");
		}
	}
}

 

Union-find!

 

노드들과 간선들을 입력받고

노드1과 노드2가 connected 되어있는지 확인하는 알고리즘