기록을

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

전형적인 Union-Find 문제이다. 또는 분리 집합 유형이라고 불린다.

n이 포함된 집합을 나타내는 정수 배열로 r[n]을 사용하자.

먼저 0부터 n까지, r[n]을 자기 자신으로 초기화한다.

그리고 주어지는 명령에 따라서 union과 find를 구현한다.

0, a, b가 주어지면 a가 속한 곳을 b가 속한 곳으로 수정해준다.

가령, a가 속한 집합이 3이고, 3이 속한 집합이 2라면 r[3]이 b가 속한 집합으로 수정되어야 하기 때문에,

r[getParent(a)] = getParent(b) 의 로직을 사용한다.

getParent의 경우, r[n]=n이 나올 때까지, 즉 최상단 부모노드일 때까지 getParent가 실행되어야 한다.

#include<iostream>
using namespace std;

int r[1000001];
int n, m;

int getParent(int num) { //find
	if (r[num] == num)
		return num;
	else{
		return r[num] = getParent(r[num]);
	}
}

void join(int a, int b) { // union
	//a의 부모를 b의 부모로 수정
	r[getParent(a)] = getParent(b);



int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> m;

	for (int i = 0; i <= n; i++) {
		r[i] = i;
	}

	while (m--) {
		int cmd, a, b;
		cin >> cmd >> a >> b;

		if (cmd == 0) {
			join(a, b);
		}
		else {
			if (getParent(a) == getParent(b))
				cout << "YES\n";
			else
				cout << "NO\n";
		}
	}

	return 0;
}

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

MST를 구현해주면 되고, 크루스칼 알고리즘을 이용한다.

크루스칼 알고리즘은 유니온 파인드를 그대로 옮겨 놨다고 봐도 상관이 없다.

0. 유니온 파인드를 활용하기 때문에, 최상위 부모노드의 값을 자기 자신으로 초기화한다.

1. 간선 정보를 비용 오름차순으로 정렬한다.

2. 간선의 시작점과 끝점을 union해보면서, 같은 그룹에 속해있지 않다면, union 해주고 간선 비용을 추가해준다.

이미 같은 그룹이라면 연결되어 있다는 의미이기 때문에 비용에 더해주지 않고 스킵한다.

3. 모든 노드를 연결하는데에 필요한 간선의 개수는 n-1개이다. 따라서 n-1개 만들었으면 그만두고 반복문을 빠져나오자.

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

유니온파인드를 활용하는 문제이다.

주의할 점은, 항상 특정 노드의 최상위 부모가, 업데이트가 되어있지 않을 수 있다는 생각을 하고, 구현을 해야한다는 것이다.

따라서 최상위 부모를 찾으러 올라갈 때도, 항상 getParent 함수를 호출하면서 올라간다.

마찬가지로 union연산을 할 때에도, a혹은 b의 최상위 부모가 제대로 갱신이 되어있지 않을 수 있기 때문에 마찬가지로 갱신을 하면서 찾아준다.

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

n개의 선분들이 각각 두 개의 좌표로 표현되어서 주어진다.

이 각각의 선분이 교차하는 경우에 같은 그룹으로 본다고 했을 때, 그룹의 수와 가장 멤버수가 많은 그룹에 속한 선분의 개수는?

[알고리즘]

1. 입력으로 들어오는 모든 선분들에 대해서 교차판별을 진행한다.

2. union-find를 활용해서, 교차한다면 같은 그룹으로 root를 묶어준다.

3. root인 선분의 개수를 파악한다. (root의 개수가 곧 그룹의 개수)

4. 그룹을 이루는 선분의 수가 가장 많은 그룹의 선분의 수를 파악한다.

[풀이]

교차 판별은 CCW를 활용한다. 1. 선분 A에 대해서 B의 각 점과 CCW를 돌리고, 2. 선분 B에 대해서 A의 각 점과 CCW를 돌린다.

1과 2의 결과가 모두 음수여야 기본적으로 교차할 수 있는 각도로 주어져있는 상태이다.

추가적으로 문제에서 관통하지 않고 딱 만나기만 해도 교차로 간주한다고 했으므로 위 조건에 0이 되는 경우까지 추가해야 한다.

이제 놓여있는 상태에 따라서 만날 수도 있고 아닐 수도 있다.

선분 A를 이루는 두 점의 x좌표가 선분 B를 이루는 두 점의 X좌표 모두보다 작다면 당연히 만날 수 없다. y좌표의 경우도 마찬가지.

그리고 선분 B에 대해서도 마찬가지이다. 이럴 경우에는 위의 CCW결과의 곱이 둘 다 음수로 나오더라도 만날 수 없는 경우이다.

이를 진행할 때, 만난다고 판단되는 경우 union작업을 해줘야 한다. union-find를 진행하기 위해, 부모 배열(r[])을 모두 자기 자신으로 초기화 해준다.

그리고 만난다고 판단되는 경우 union해준다.

이 작업을 마쳤다 하더라도, 모든 노드의 r[] 값이 최상위 부모로 갱신되었다는 보장이 없다. 따라서 getParent를 모든 지점에 대해 수행하여 r[] 값을 최상위 부모로 갱신해준다.

cnt[] 배열은 인덱스를 최상위 부모로 하는 선분의 수이다. cnt[1] = 3이라면, 1을 최상위 부모로하는 노드가 3개 있다는 것이다.

따라서 cnt[] 값이 0초과인 경우를 카운트 해주면, 그룹의 수를 셀 수 있다.

cnt[] 값이 최대인 곳이 최대 크기의 그룹일 것이다.

복습