부록 D - Union-Find

[Jinsun-Lee]

리드미

• 개념
• 문제집
  • 1717 | 집합의 표현
  • 7511 | 소셜 네트워킹 어플리케이션
  • 1976 | 여행 가자
  • 20040 | 사이클 게임
  • 18116 | 로봇 조립
  • 17619 | 개구리 점프
  • ★14595 | 동방 프로젝트 (Large)
  • 10775 | 공항
  • 2162 | 선분 그룹

[Jinsun-Lee]

1717. 집합의 표현

#include <iostream>
#include <vector>
using namespace std;

vector<int> p(1000001, -1);

int find(int x) {
	//while (p[x] > 0) x = p[x];
	if (p[x] < 0) return x;
	return p[x] = find(p[x]); //최적화2. 경로 압축
}

bool uni(int u, int v) {
	u = find(u); // int u = find(a);
	v = find(v);
	if (u == v) return false; //이미 같은 그룹
	
	//최적화1. union by rank	
	if (p[v] < p[u]) swap(u, v); // V의 랭크가 더 큼 = 자식이 더 길어서 U>=V의 랭크로 만듦
	if (p[u] == p[v]) p[u]--; // 랭크가 같은 경우 랭크 1 증가(근데 음수라서 빼야 해)
	p[v] = u; // v를 u의 자식으로 만든다
	return true;
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int n, m; cin >> n >> m;
	int q, a, b;
	while (m--) {
		cin >> q >> a >> b;
		if (q == 1) cout << ((find(a) == find(b) ? "YES" : "NO")) << "\n";
		else uni(a, b);
	}
	return 0;
}

[Jinsun-Lee]

14595. 동방 프로젝트 (Large)

// 2372 0 561 근데 유니온파인드로 안 풂
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

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

	int N, M;  cin >> N >> M;

	int x, y;
	vector<pair<int, int>> vec;
	for (int i = 0; i < M; ++i) {
		cin >> x >> y;
		vec.push_back({ x, y });
	}
	sort(vec.begin(), vec.end());
	
	int xx = 0, yy = 0;
	for (int i = 0; i < M; ++i) {
		if (yy < vec[i].first) {
			N -= yy - xx;
			xx = vec[i].first;
			yy = vec[i].second;
		}
		else {
			if (yy < vec[i].second) yy = vec[i].second;
		}
	}
	
	N -= yy - xx;
	cout << N;
	return 0;
}

// 6120 12 958
vector<int> p; // (1000001, -1);

// 정석적인 유니온파인드 코드

int main() {
    cin >> N >> M;
    
    if (M == 0) {
		cout << N << "\n";
		return 0;
	}

	p.assign(N + 1, -1);

	// 사이즈를 M으로 한정해 줘
	vector<pair<int, int>> vec(M); 
	for (int i = 0; i < M; ++i) cin >> vec[i].first >> vec[i].second;

	sort(vec.begin(), vec.end());
	
	int x = vec[0].first, y = vec[0].second;

	// i=1부터 시작
	for (int i = 1; i < M; ++i) { 
		int xx = vec[i].first, yy = vec[i].second;

		if (xx <= y) y = max(y, yy);
		else {
			// 구간 끊기기
			for (int j = x; j < y; ++j) uni(j, j +1);				
			x = xx; y = yy;
		}
	}
	
	// 마지막 구간 union
	for (int j = x; j < y; ++j) uni(j, j + 1);
    
	int cnt = 0;
	for (int i = 1; i <= N; ++i) if (p[i] < 0) ++cnt;
	cout << cnt;
	return 0;
}

#include <tuple> // tie를 쓰기 위해

int main() {
	sort(vec.begin(), vec.end());

	// 이렇게 풀어도 돼
	int cnt = N;
	int x = 0, y = 0, xx, yy;
	for (int i = 0; i < M; ++i) {
		// auto [xx, yy] = vec[i]; // 17 이상만 돼 
		tie(xx, yy) = vec[i];

		x = max(x, xx);
		y = max(y, yy);

		for (int i = x; i < y; ++i) {
			if (uni(i, i + 1)) --cnt;
		}
		x = y;
	}

	cout << cnt;
	return 0;
}

[Jinsun-Lee]

1976 | 여행 가자

int main() {
	cin >> N >> M;
   
	fill(p, p + MX, -1);

	int tmp; 
	for (int i = 1; i <= N; ++i) { // 범위 주의
		for (int j = 1; j <= N; ++j) {
			cin >> tmp;
			if (tmp) uni(i, j);
		}
	}
	
	// M개 만큼을 돌면서 그룹이 다르면 break 걸고 "NO" 출력
	int grp; cin >> tmp;
	grp = find(tmp);

	for (int i = 2; i <= M; ++i) {
		cin >> tmp;
		if (grp != find(tmp)) {
			cout << "NO";
			return 0;
		}
	}
	cout << "YES";
	return 0;
}

[Jinsun-Lee]

10775 | 공항

[Jinsun-Lee]

17619 | 개구리 점프

[Jinsun-Lee]

18116 | 로봇 조립

[Jinsun-Lee]

2162 | 선분 그룹

[Jinsun-Lee]

어려워!!!

동방문제, 개구리, 공항 문제

[Jinsun-Lee]

개구리

p[u]+=p[v];
p[v]= u;

int x = tree[0].x, y = tree[0].y;
for (int i = 1; i <= N; ++i) {
    int xx = tree[i].x, yy = tree[i].y;
    if (xx <= y) {
        uni(tree[i - 1].idx, tree[i].idx);
        y = max(y, yy);
    }
    else y = tree[i].y;
}

[Jinsun-Lee]

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Pos {
	int x, y, idx;
};

bool cmp(Pos a, Pos b) {
	return a.x < b.x;
}

//const int MX = 100'001;
//vector<int> p(MX, -1);
vector<int> p;

int find(int x) {
	if (p[x] < 0) return x;
	return p[x] = find(p[x]);
}

void uni(int u, int v) {
	u = find(u);
	v = find(v);
	if (u == v) return;
    
    /*
    if (p[v] < p[u]) swap(u, v);
	//if (p[v] == p[u]) --p[u];
	p[u] += p[v];
	p[v] = u;
    */
    
	if (v < u) swap(u, v);
	p[u] = v; // 우측 유지하게
    
    //p[v] = u;
}

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

	int N, Q; cin >> N >> Q;
	p.assign(N + 1, -1);
	vector<Pos> tree(N+1);

	int a, b;
	for (int i = 1; i <= N; ++i) {
        //cin >> a >> b >> c;
		//tree[i] = { a, b, i };
		cin >> tree[i].x >> tree[i].y >> a;
		tree[i].idx = i;
	}

	sort(tree.begin(), tree.end(), cmp);
    
    /*
    int x = tree[0].x, y = tree[0].y;
	for (int i = 1; i <= N; ++i) {
		int xx = tree[i].x, yy = tree[i].y;
		if (xx <= y) {
			uni(tree[i - 1].idx, tree[i].idx);
			y = max(y, yy);
		}
		else y = tree[i].y;
	}
    */
    
	int y = tree[1].y;
	for (int i = 2; i <= N; ++i) {
		int xx = tree[i].x, yy = tree[i].y;
		if (xx <= y) {
			uni(tree[i - 1].idx, tree[i].idx);
			y = max(y, yy);
		}
		else y = yy;
	}
    
    /*
    for (int i = 0; i < xx.size() - 1; i++) {
		if (xx[i + 1].st <= xx[i].en) {
			xx[i + 1].en = max(xx[i + 1].en, xx[i].en);
			uni(xx[i + 1].idx, xx[i].idx);
		}
	}
    */

	while (Q--) {
		cin >> a >> b;
		if (find(a) == find(b)) cout << "1\n";
		else cout << "0\n";
	}
	return 0;
}