[백준] 4014번: 도로

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

4014번: 도로

문제 요약

`N`개의 정점과 `M`개의 간선으로 이루어진 무방향 그래프가 주어진다. 각 간선은 두 종류 중 하나인데, 편의상 A간선 또는 B간선이라 하자(문제에서는 "자갈 도로"와 "콘크리트 도로"라고 표현함). 이때 A간선을 $K$개 포함하는 스패닝 트리를 찾고, 만약 존재하지 않는다면 no solution을 출력하라.

제한

`1 le N le 20\ 000`

`1 le M le 100\ 000`

`0 le K le N-1`

 

(N이 1일 수는 없을 것 같아서 assert문으로 확인해 본 결과, 모든 데이터에서 N이 1보다 컸다.)

풀이

먼저, 주어진 그래프를 B간선으로만 연결된 컴포넌트들로 분리하자(부속된 B간선이 존재하지 않는 정점의 경우, 그 정점 자체를 하나의 컴포넌트로 간주한다). 그러면 각 컴포넌트들은 A간선으로 연결할 수밖에 없는데, 1)연결되지 않는 컴포넌트가 존재하거나 2)모든 컴포넌트들을 하나로 연결할 수 있다 하더라도 `K`개보다 많은 A간선이 필요할 경우, 조건에 맞는 스패닝 트리는 존재하지 않는다.

 

위의 두 경우에 해당하지 않는다면 컴포넌트들을 (컴포넌트의 개수 - 1)개의 A간선을 사용하여 서로 연결할 수 있다. 일단, 컴포넌트들을 모두 연결하고(여러가지 연결 방법이 있을 경우 아무렇게나 연결한다), 각 컴포넌트에 속하는 정점들도 최소한의 B간선을 사용하여 임의로 연결하여 스패닝 트리를 만들었다고 하자. 컴포넌트들을 연결할 때 정확히 `K`개의 A간선을 사용했다면 문제의 답을 구한 것이 되지만, 만약 `K`개보다 적은 수의 A간선을 사용했다면 추가적인 A간선을 포함하도록 스패닝 트리를 수정해 주어야 한다. 어떻게 해야 할까?

 

아직 사용하지 않은 A간선 하나를 스패닝 트리에 추가해 보자. 그러면 사이클이 하나 생기게 되는데, 사이클에 B간선이 1개라도 포함되어 있을 경우, B간선 하나를 삭제함으로써 다시 트리 형태로 만들어줄 수 있다. 만약 A간선을 추가했을 때 생기는 사이클이 A간선으로만 이루어지게 될 경우, 해당 A간선은 추가할 수 없다(사이클 내의 다른 A간선 하나를 삭제한다면 추가할 수는 있지만, 하나를 추가하기 위해 하나를 삭제해야 하므로 아무런 의미가 없다). 이와 같이 트리 형태를 유지하며 `K`개를 모두 사용할 때까지 그리디하게 A간선들을 추가해줄 수 있고, 이렇게 했을 때에도 `K`개를 채울 수 없다면 찾고자 하는 스패닝 트리는 존재하지 않는다.

구현

disjoint set을 이용하여 구현할 수 있다. 아래와 같이 변수 이름을 정했다.

 

• jagal: A간선(=자갈 도로)들을 저장하는 벡터
• conc: B간선(=콘크리트 도로)들을 저장하는 벡터
• ans: 구하고자 하는 스패닝 트리에 포함되는 간선들을 저장하는 벡터
• spanTree: 스패닝 트리를 구축할 때 사용하는 disjoint set
• concComp: B간선들로만 연결된 컴포넌트들을 얻을 때 사용하는 disjoint set

우선 concComp를 이용하여 컴포넌트들을 얻은 후, A간선들로 컴포넌트끼리 연결해 준다. 이때 사용한 A간선은 ans에 추가하고, spanTree도 동시에 관리해야 한다. 여기까지 수행했을 때, 컴포넌트가 2개 이상 남아있거나 `K`개보다 많은 A간선을 사용했다면 no solution을 출력한다.

 

추가해야 할 나머지 A간선 수만큼 ans에 A간선을 추가해 주는데, 이때 A간선으로만 이루어진 사이클이 만들어지는지 판단하기 위해 spanTree를 이용한다. 추가하려는 A간선의 양 끝 정점이 같은 집합에 속한다면, 해당 간선 추가 시 A간선으로만 이루어진 사이클이 만들어지게 된다(지금까지 스패닝 트리에 A간선만 추가했기 때문). 이렇게 A간선들을 추가해 주었을 때, 아직도 A간선을 더 추가해야 하는 상황이라면 no solution을 출력한다.

 

마지막으로, 스패닝 트리를 완성하기 위해 필요한 B간선들을 추가해 준다. 각 B간선에 대하여 사이클 생성 여부를 확인하면서 하나씩 추가하면 된다.

 

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

typedef pair<int, int> pii;

struct myset{
	myset(int n){
		p.resize(n, -1);
	}
	int find(int s){
		int e = s;
		while(p[e] >= 0){
			e = p[e];
		}
		while(s != e && p[s] != e){
			int t = p[s];
			p[s] = e;
			s = t;
		}
		return e;
	}
	void merge(int x, int y){
		x = find(x), y = find(y);
		if(x == y) return;
		if(p[x] < p[y]){
			p[x] += p[y];
			p[y] = x;
		}
		else{
			p[y] += p[x];
			p[x] = y;
		}
	}
	vector<int> p;
};

int main(){
	ios::sync_with_stdio(0); cin.tie(0);
	int n, m, k;
	cin >> n >> m >> k;
	vector<pii> jagal, conc;
	vector<pair<pii, int> > ans;
	myset spanTree(n), concComp(n);
	int concCompCnt = n;
	for(int i = 0; i < m; i++){
		int u, v, c;
		cin >> u >> v >> c;
		u--, v--;
		if(c) {
			conc.push_back({u, v});
			int r1 = concComp.find(u), r2 = concComp.find(v);
			if(r1 != r2){
				concComp.merge(r1, r2);
				concCompCnt--;
			}
		}
		else jagal.push_back({u, v});
	}
	for(auto e : jagal){
		int r1 = concComp.find(e.first), r2 = concComp.find(e.second);
		if(r1 != r2){
			concComp.merge(r1, r2);
			spanTree.merge(spanTree.find(e.first), spanTree.find(e.second));
			ans.push_back({e, 0});
			concCompCnt--;
			k--;
		}
	}
	if(concCompCnt > 1 || k < 0){
		cout << "no solution";
		return 0;
	}
	for(auto e : jagal){
		if(!k) break;
		int r1 = spanTree.find(e.first), r2 = spanTree.find(e.second);
		if(r1 != r2){
			spanTree.merge(r1, r2);
			ans.push_back({e, 0});
			k--;
		}
	}
	if(k){
		cout << "no solution";
		return 0;	
	}
	for(auto e : conc){
		int r1 = spanTree.find(e.first), r2 = spanTree.find(e.second);
		if(r1 != r2){
			spanTree.merge(r1, r2);
			ans.push_back({e, 1});
		}
	}
	for(auto e : ans){
		cout << e.first.first + 1 << ' ' <<  e.first.second + 1 << ' ' << e.second << '\n';
	}
}