백준 3505 Kingdom Roadmap

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

어떤 노드 x에 대하여 다른 모든 노드와 한 개 이상의 cycle이 존재한다면 어떤 간선을 지워도 x에서 모든 노드에 대한 연결성이 사라지지 않습니다.

추가해야 하는 간선의 개수가 (리프 노드의 개수+1)/2 임을 증명해 봅시다.

  1. cycle이 생기기 위해서는 degree의 개수(연결된 노드의 개수)가 2 이상이여야 함은 자명합니다. 따라서 추가해야 하는 간선의 개수는 최소 (리프 노드의 개수+1)/2 입니다.

  2. 루트(1)의 모든 subtree에 대하여(추가되기 전 트리 기준), 다른 subtree와 연결되는 간선이 있다면 이 subtree는 항상 연결성을 유지합니다.

  3. 리프 노드를 dfs 방문 순서에 따라 정렬해 봅시다. 또, 모든 리프노드의 개수를 N이라 합시다. N이 짝수인 경우 모든 리프노드에 대하여 $ a_i $ 와 $ a_{i+N/2} $ 를 연결한다면 모든 subtree가 다른 subtree와 연결됩니다. 귀류법으로 쉽게 증명할 수 있으므로 넘어가도록 하겠습니다.

  4. N이 홀수인 경우 짝수와 마찬가지로 연결한 후, $a_N $ 과 $ a_0 $를 연결하면 됩니다.

증명되었으니 코드를 보도록 합시다.

#include<bits/stdc++.h>
#define pb push_back
#define ff first
#define ss second
using namespace std;
typedef pair<int,int> pii;
const int SZ=100005;
vector<int> graph[SZ];
vector<pii> v;
vector<pii> ans;
int dfsn[SZ];
int deg[SZ];
int p;
void dfs(int par, int x){
	dfsn[x]=++p;
	for(int nxt:graph[x]){
		if(par==nxt) continue;
		dfs(x,nxt);
	}
}
int main(void){
	ios::sync_with_stdio(false); cin.tie(NULL);
	int n; cin>>n;
	for(int i=1;i<n;i++){
		int x,y; cin>>x>>y;
		graph[x].pb(y);
		graph[y].pb(x);
		deg[x]++; deg[y]++;
	}
	dfs(1,1);
	for(int i=1;i<=n;i++){
		if(deg[i]==1) v.pb({dfsn[i],i});
	}
	sort(v.begin(),v.end());
	int sz=v.size();
	for(int i=0;i<sz/2;i++){
		ans.pb({v[i].ss,v[i+sz/2].ss});
	}
	if(sz%2==1) ans.pb({v[0].ss,v[sz-1].ss});
	cout<<ans.size()<<'\n';
	for(pii x:ans) cout<<x.ff<<" "<<x.ss<<'\n';
	return 0;
}