백준 9938번 : 방 청소 dis-joint set C++

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

9938번: 방 청소

Union&Find 알고리즘(dis-joint set)을 이용해서 풀어야 하는 문제다

 

풀이를 생각해내기 어려운 문제

 

 

#include <bits/stdc++.h>
using namespace std;


int n, l, unf[300001];
bool isfull[300001] ;

int Find(int x) {
	if (unf[x] < 0) return x;

	return unf[x] = Find(unf[x]);
}

void Union(int a, int b) {
	a = Find(a);
	b = Find(b);
	if (a == b) return;

	if (isfull[a]) {
		unf[a] = b;
	}
	else if (isfull[b]) {
		unf[b] = a;
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	memset(unf, -1, sizeof(unf));


	cin >> n >> l;
	for (int i = 1; i <= n; i++) {
		int a, b;
		cin >> a >> b;
		if (!isfull[Find(a)]) {
			isfull[Find(a)] = 1;
			Union(a, b);
			cout << "LADICA\n";
		}
		else if (!isfull[Find(b)]) {
			isfull[Find(b)] = 1;
			Union(a, b);
			cout << "LADICA\n";
		}
		else {
			cout << "SMECE\n";
		}
	}

	return 0;
}

백준 9938번