(백준 1717번 집합의 표현 C++) 라이님 블로그 대회 알고리즘 따라잡기 12) Union Find

Union Find 알고리즘으로 빠르게 넘어가서 하나 풀어봤다.

늘 그렇듯 라이님 블로그를 보면서 이해했다.

 

https://blog.naver.com/PostView.naver?blogId=kks227&logNo=220791837179&parentCategoryNo=&categoryNo=299&viewDate=&isShowPopularPosts=false&from=postList

 

백준 1717번

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

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <algorithm>

using namespace std;

constexpr int MAX_N = 1000000 + 1;
int p[MAX_N];

int find(int n) {
	// ★오타 주의★ 
	if (p[n] < 0) return n;
	p[n] = find(p[n]);
	return p[n];
}

void merge(int a, int b) {
	a = find(a);
	b = find(b);
	if (a == b) return;
	p[a] = b;
}

int main() {
	int n, m; scanf("%d %d", &n, &m);
	fill_n(p, n + 1, -1);
	int ncase, a, b;
	for (int i = 0; i < m; i++) {
		scanf("%d %d %d", &ncase, &a, &b);
		// 합집합
		if (ncase == 0) merge(a, b);
		// 같은 집합에 속하는지 확인
		else if (ncase == 1) {
			if (find(a) == find(b)) printf("yes\n");
			else printf("no\n");
		}
	}
	return 0;
}

 

 

오타가 있어서 맞추는데 애를 먹었지만..^^

결국 오타는 chat gpt가 찾아줌 흐흐

 

오늘 아침도 활기찬 시작을 할 수 있어서 즐겁다 🔥