ALOHA 월반 5주차 - Union Find / Minimum Spanning Tree

1. [18116] 로봇 조립 (Gold IV)

의도한 태그: Union-Find (Easy)

 

'I a b'의 쿼리는 그냥 union으로 처리하면 됩니다.

'Q c'도 find가 쓰이는 것 같은데, 부품의 개수까지 알아내야 합니다.

 

부품의 개수 = 집합의 크기 이고, 집합의 크기는 모두 1인 상태로 시작해서

union을 할 때마다 합쳐지는 두 집합의 크기의 합을 새로 저장해주면 됩니다.

const int N = 1000000;
int par[1000020], siz[1000020];
int fnd(int a){
	if (par[a] == a){ return a; }
	return par[a] = fnd(par[a]);
}
void uni(int a, int b){ int pa = fnd(a), pb = fnd(b);
	if (pa == pb){ return; }
	par[pa] = pb; siz[pb] += siz[pa];
}

void Main(){
	for (int i = 1; i <= N; i++){ par[i] = i; siz[i] = 1; }
	int q; cin >> q; while (q--){
		char typ; cin >> typ;
		if (typ == 'I'){ int a, b; cin >> a >> b; uni(a, b); }
		if (typ == 'Q'){ int a; cin >> a; cout << siz[fnd(a)] << endl; }
	}
}

2. [20040] 사이클 게임 (Gold IV)

의도한 태그: Spanning Tree (Easy)

 

MST 구할 때, 사이클이 만들어지는지 판별해봤죠?

그대로 해주면 됩니다.

int par[500020];
int fnd(int a){
	if (par[a] == a){ return a; }
	return par[a] = fnd(par[a]);
}
void uni(int a, int b){ par[fnd(a)] = fnd(b); }

void Main(){
	int n, m; cin >> n >> m;
	for (int i = 0; i < n; i++){ par[i] = i; }
	for (int ans = 1; ans <= m; ans++){
		int v, w; cin >> v >> w;
		if (fnd(v) == fnd(w)){ cout << ans; return; }
		uni(v, w);
	}
	cout << 0;
}

3. [2406] 안정적인 네트워크 (Gold III)

의도한 태그: Minimum Spanning Tree (Normal)

 

문제 조건을 읽어보면, 기본적으로 1번 컴퓨터와 다른 모든 컴퓨터는 연결되어있습니다.

그래서, 2번 정점부터 N번 정점까지만 써서 MST를 만들어주면 됩니다.

 

이유를 하나하나 살펴보면, 각각 연결이 끊어져도 연결성이 유지되기 위해서는

• 1번 정점이 끊어질 때: 2번 정점부터 N번 정점까지 연결되어있어야 합니다.
• 다른 정점이 끊어질 때: \( v \rightarrow 1 \rightarrow w \)의 경로가 항상 있으니 걱정 안 해도 됩니다.
• \( 1 \leftrightarrow v \)가 끊어질 때: \( v \)에서 다른 모든 정점으로 이동할 수 있어야 합니다.
  • 2번 정점부터 N번 정점까지 연결이 되어있다면, \( v \rightarrow w \rightarrow 1 \)의 경로가 가능하니 걱정 안 해도 됩니다.
• \( v \leftrightarrow w \)가 끊어질 때: \( v \)와 \( w \)가 계속 연결되어있어야 합니다.
  • \( v \rightarrow 1 \rightarrow w \)의 경로가 항상 있으니 걱정 안 해도 됩니다.

그러니, 실질적인 조건은 2~N번 정점이 (1번 정점을 제거하더라도) 연결되어있어야 한다 이고,

그렇기 때문에 2~N번 정점만 보는 MST로 AC를 받을 수 있습니다.

int par[1020];
int fnd(int a){ return par[a] = (par[a] == a ? a : fnd(par[a])); }
void uni(int a, int b){ par[fnd(b)] = fnd(a); }

void Main(){
	int n, m; cin >> n >> m;
	for (int i = 1; i <= n; i++){ par[i] = i; }
	while (m--){
		int v, w; cin >> v >> w;
		uni(v, w);
	}
	vector<pi3> edg;
	for (int v = 1; v <= n; v++){
		for (int w = 1; w <= n; w++){
			int x; cin >> x;
			if (1 < v && v < w){ edg.push_back({ {v, w}, x }); }
		}
	}
	sort(all(edg), [](pi3 a, pi3 b){ return a.sc < b.sc; });
	ll ans = 0; vector<pi2> res;
	for (pi3 p : edg){
		int v = p.fr.fr, w = p.fr.sc; int x = p.sc;
		if (fnd(v) != fnd(w)){ ans += x; res.push_back({v, w}); uni(v, w); }
	}
	cout << ans << ' ' << res.size() << endl;
	for (pi2 p : res){ cout << p.fr << ' ' << p.sc << endl; }
}

4. [1414] 불우이웃 돕기 (Gold III)

의도한 태그: Minimum Spanning Tree (Easy)

 

기부하는 랜선의 길이를 최대화하려면, 남기는 랜선의 길이를 최소화해야 합니다.

그럼, 컴퓨터를 모두 연결시키면서 랜선의 길이를 최소화하는 문제가 되고, 이건 자명히 MST를 만들어서 풀면 됩니다.

inline int f(char ch){
	if ('a' <= ch && ch <= 'z'){ return ch-96; }
	if ('A' <= ch && ch <= 'Z'){ return ch-64+26; }
}

int par[60];
int fnd(int a){ return par[a] = (par[a] == a ? a : fnd(par[a])); }
void uni(int a, int b){ par[fnd(b)] = fnd(a); }

void Main(){
	vector<pi3> edg;
	int n; cin >> n; int sum = 0;
	for (int i = 1; i <= n; i++){
		for (int j = 1; j <= n; j++){
			char ch; cin >> ch;
			if (ch != '0'){ edg.push_back({ {i, j}, f(ch) }); sum += f(ch); }
		}
	}
	for (int i = 1; i <= n; i++){ par[i] = i; }
	sort(all(edg), [](pi3 a, pi3 b){ return a.sc < b.sc; });
	int ans = 0, cnt = 0;
	for (pi3 p : edg){
		int v = p.fr.fr, w = p.fr.sc; int x = p.sc;
		if (fnd(v) != fnd(w)){ ans += x; cnt += 1; uni(v, w); }
	}
	if (cnt != n-1){ cout << -1; } else{ cout << sum-ans; }
}

5. [16402] 제국 (Gold II)

의도한 태그: Union-Find (Normal)

 

종주국을 루트로 잡아가면서 Union-Find를 하면 됩니다.

두 종주국 간의 전쟁은 간단한 union이지만, 종주국과 속국의 전쟁은 어떻게 처리해야 할까요?

 

만약 종주국이 이긴다면, 아무런 변화가 없습니다.

하지만, 속국이 이긴다면, 루트 정점 ( = 종주국)을 그 속국으로 바꿔줘야 합니다.

다행히도, 이건 par[lose] = win으로 해주면 됩니다.

 

평소의 union과는 다르게, find(winner)를 해버리면 종주국으로 돌아가버리니 주의하세요.

또한, 루트를 조정하는 것이니 par[loser]와 par[winner]를 둘 다 변경해야 합니다.

par = [ i for i in range(520) ]
def fnd(a):
    #print(a, par[a])
    if par[a] == a: return a
    par[a] = fnd(par[a]); return par[a]
def uni(a, b):
    pa, pb = fnd(a), fnd(b)
    if pa == pb:
        par[b] = a; par[a] = a
    else: par[pb] = pa

cvt, tvc = dict(), dict()

n, m = map( int, input().split() )
for i in range(1, n+1):
    s = input().strip()
    cvt[s] = i; tvc[i] = s
for _ in range(m):
    s1, s2, x = input().split(','); x = int(x)
    i1, i2 = cvt[s1], cvt[s2]
    if x == 2: i1, i2 = i2, i1
    #print(s1, s2, i1, i2)
    uni(i1, i2)
ans = []
for i in range(1, n+1):
    if par[i] == i: ans.append(tvc[i])
ans.sort()
print(len(ans))
for s in ans: print(s)

6. [23743] 방탈출 (Gold II)

의도한 태그: Minimum Spanning Tree (Normal)

 

각 방을 정점으로 놓고, 비상 탈출구까지 정점으로 만들어봅시다.

그럼, 모든 방들을 비상 탈출구에 최소 비용으로 연결시키는 문제가 됩니다.

 

그런데, 모든 방을 비상 탈출구에 연결시키면 모든 방들끼리도 간접적인 연결이 됩니다.

그러니, 이는 모든 방들과 비상탈출구를 최소 비용으로 연결시키는 문제가 됩니다.

 

모든 정점을 최소 비용으로 연결시키는 문제니, 간단히 MST로 슥삭해주면 됩니다.

int par[200020];
int fnd(int a){ return par[a] = (par[a] == a ? a : fnd(par[a])); }
void uni(int a, int b){ par[fnd(b)] = fnd(a); }

void Main(){
	int n, m; cin >> n >> m;
	for (int i = 0; i <= n; i++){ par[i] = i; }
	vector<pi3> edg;
	while (m--){
		int v, w, x; cin >> v >> w >> x;
		edg.push_back({ {v, w}, x });
	}
	for (int i = 1; i <= n; i++){ int x; cin >> x; edg.push_back({ {i, 0}, x }); }
	sort(all(edg), [](pi3 a, pi3 b){ return a.sc < b.sc; });
	ll ans = 0;
	for (pi3 p : edg){
		int v = p.fr.fr, w = p.fr.sc; int x = p.sc;
		if (fnd(v) != fnd(w)){ ans += x; uni(v, w); }
	}
	cout << ans;
}

7. [10775] 공항 (Gold II)

의도한 태그: Union-Find (Hard)

 

각 비행기에 대해서, 가능한 가장 큰 번호에 도킹하는 게 최적입니다.

이는 나중에 도킹될 비행기들이 가지는 후보군을 생각해보면 됩니다.

 

그럼 그건 어떻게 빠르게 찾을까요?

각 비행기에 대해서 '내 왼쪽에 있는 게이트 중 도킹이 가능한 게이트'를 저장하면 됩니다.

그리고 게이트에 도킹을 할 때마다, 그 포인터를 왼쪽으로 연결시켜주면 됩니다.

 

이게 왜 Union-Find에 있나면, '도킹이 가능한 게이트'를 parent 배열에 저장한다고 생각해보면 편합니다.

const int N = 100000;
int par[100020];

int fnd(int a){
	if (par[a] == a){ return a; }
	return par[a] = fnd(par[a]);
}

void Main(){
	for (int i = 1; i <= N; i++){ par[i] = i; }
	int _, n; cin >> _ >> n;
	for (int ans = 0; ans < n; ans++){
		int x; cin >> x;
		int pos = fnd(x);
		if (pos == 0){ cout << ans; return; }
		par[pos] = pos-1;
	}
	cout << n;
}

8. [17132] 두더지가 정보섬에 올라온 이유 (Platinum V)

의도한 태그: Spanning Tree (Hard)

 

가중치가 큰 간선부터 연결을 해봅시다.

그럼, \( v \leftrightarrow w \)를 연결할 때는 이보다 가중치가 크거나 같은 간선들만 있음이 보장됩니다.

 

그렇다는 말은, \( v \)가 속한 컴포넌트에서 \( w \)가 속한 컴포넌트로 이동할 때는 반드시 \( v \leftrightarrow w \)의 간선을 사용하게 될테고, 이는 현재 상태에서 가중치가 가장 작은 간선이니

\( v \)가 속한 컴포넌트에서 \( w \)가 속한 컴포넌트로 이동하는 모든 경로의 만족도는 \( v \leftrightarrow w \)의 가중치가 됩니다.

 

\( v \)가 속한 컴포넌트에서 \( w \)가 속한 컴포넌트로 이동하는 모든 경로의 수는

\( v \)가 속한 컴포넌트의 정점 개수 × \( w \)가 속한 컴포넌트의 정점 개수 가 됩니다.

 

그러니, 우선 가중치를 내림차순으로 정렬한 뒤, union을 할 때 '컴포넌트별 정점 개수'를 관리하면서 만족도의 합을 경로의 수 × 간선의 가중치 만큼 증가시켜주면 됩니다.

ll ans = 0;

int par[100020], siz[100020];
int fnd(int a){
	if (par[a] == a){ return a; }
	return par[a] = fnd(par[a]);
}
void uni(int a, int b, ll x){ int pa = fnd(a), pb = fnd(b);
	ans += x*siz[pa]*siz[pb];
	par[pa] = pb; siz[pb] += siz[pa];
}

void Main(){
	int n; cin >> n;
	for (int i = 1; i <= n; i++){ par[i] = i; siz[i] = 1; }
	priority_queue<pi3> pq;
	for (int i = 1; i < n; i++){
		int v, w, x; cin >> v >> w >> x;
		pq.push({ x, {v, w} });
	}
	while (!pq.empty()){
		int x = pq.top().fr;
		int v = pq.top().sc.fr, w = pq.top().sc.sc;
		pq.pop(); uni(v, w, x);
	}
	cout << ans;
}

9. [8225] Tour de Byteotia (Platinum III)

의도한 태그: Spanning Tree (Hard)

 

\( v \le k \)에 대해, \( v \)를 포함하는 사이클이 생기면 안 되는 문제입니다.

 

\( v \)를 포함하지 않는 사이클은 언제나 만들어도 되니, 기본적으로는 Spanning Tree를 만들되 \( u \gt k \)들끼리의 사이클은 허용해주면 됩니다.

 

저의 경우는 일단 \( v, w \le k \)와 \( v, w \gt k \)를 'Spanning Tree'와 '항상 연결'로 처리해준 뒤,

\( v \le k, w \gt k \)의 경우를 나중에 처리해줬습니다.

pi2 edg[2000020];
int par[1000020];

int fnd(int a){
	if (par[a] == a){ return a; }
	return par[a] = fnd(par[a]);
}
void uni(int a, int b){
	int pa = fnd(a), pb = fnd(b);
	par[pa] = pb;
}

vector<pi2> ans;

void Main(){
	int n, m, k; cin >> n >> m >> k;
	for (int i = 1; i <= n; i++){ par[i] = i; }
	for (int i = 1; i <= m; i++){ cin >> edg[i].fr >> edg[i].sc; }
	for (int i = 1; i <= m; i++){
		int a = edg[i].fr, b = edg[i].sc;
		if (a <= k && b <= k){
			int pa = fnd(a), pb = fnd(b);
			if (pa == pb){ ans.push_back({a, b}); }
			else{ uni(a, b); }
		}
		if (a > k && b > k){
			uni(a, b);
		}
	}
	for (int i = 1; i <= m; i++){
		int a = edg[i].fr, b = edg[i].sc;
		if ( (a <= k) ^ (b <= k) ){
			int pa = fnd(a), pb = fnd(b);
			if (pa == pb){ ans.push_back({a, b}); }
			else{ uni(a, b); }
		}
	}
	cout << ans.size() << endl;
	for (pi2 p : ans){ cout << p.fr << ' ' << p.sc << endl; }
}