BOJ 16230 우리는 진실을 잊고 살잖아

문제 링크입니다.

이게 웰노운이라고요?

제2회 웰노운컵에 출제된 문제입니다. 여기 문제 치고 진짜 웰노운인 문제가 없던데…

여튼 관찰을 해봅시다. G가 연결 그래프인지 아닌지에 따라 답이 갈릴 것입니다. 각각의 경우에, 우리는 간선의 순서를 적절히 배치해서 최대한 빠르게, 또 느리게 그 그래프가 연결 그래프인지 아닌지를 판단할 수 있게끔 만들어 주어야 합니다.

G가 연결 그래프라면

G의 스패닝 트리에 들어가는 간선들을 쭉 밀어넣으면 N-1 개의 간선만으로 G가 연결 그래프임을 알 수 있고 이것이 필요한 간선 수의 최솟값입니다.

G가 최대한 늦게 연결 그래프임을 알아차리려면, 역으로 최소한의 간선을 제거해 G의 연결이 끊기도록 만들어야 합니다. 이름이야 Global Min Cut을 구하는 문제가 되고, 스토어-바그너 알고리즘을 이용해 이를 구할 수 있습니다. C개의 간선을 날려서 G의 연결을 끊을 수 있다면, 연결 그래프임을 알아채기 위해 필요한 간선의 최댓값은 N(N-1)/2 -C +1 입니다.

G가 연결 그래프가 아니라면

G가 연결 그래프가 아님을 알아채려면, 다른 모든 정점과 연결되어 있지 않은 정점 덩어리가 있다는 사실을 알아내야 합니다. 어떤 연결 요소의 크기를 S라고 하면, 그 연결 요소가 연결 요소 외의 정점들과 연결되어 있지 않다는 사실을 알기 위해 S(N-S)개의 간선이 없음을 알아야 합니다. 따라서 확인해야 하는 간선 수의 최솟값은 S(N-S) 중 가장 작은 것입니다. 이는 S가 최소인 연결 요소를 골라서 달성할 수 있습니다.

그래프 G의 각 연결 요소를 하나의 정점으로 생각해 봅시다. 그렇게 만든 그래프가 연결 그래프임을 최대한 빨리 알아내려면, 연결 요소들을 잇는 스패닝 트리를 찾아내야 합니다. 이는 거꾸로 최대한 많은 간선을 확인해 우리의 그래프가 연결 그래프가 아님을 알아채기 위해 연결 요소의 스패닝 트리를 이루는 간선을 제외한 모든 간선을 들쑤셔 보는 방법을 쓸 수 있다는 뜻입니다. G의 연결 요소의 개수를 C라고 하면, 연결 그래프가 아님을 알아채기 위해 필요한 간선 수의 최댓값은 N(N-1)/2 - (C-1) +1 개입니다.

코드

#include<bits/stdc++.h>
using namespace std;
int n, m, cnt;
vector<vector<int>> e;
int g[543][543];
bool vis[543], del[543];
int d[555];

int dfs(int now){
	vis[now] = 1;
	int ret = 1;
	for(int nxt : e[now]) if(!vis[nxt]) ret += dfs(nxt);
	return ret;
}

int min_cut(int& s, int& t){
	memset(d, 0, sizeof(d));
	memset(vis, 0, sizeof(vis));
	int ret = 0;
	for(int i = 1; i <= n; i++){
		int idx = -1, mx = -1;
		for(int j = 1; j <= n; j++){
			if(del[j] | vis[j]) continue;
			if(d[j] > mx) idx = j, mx = d[j];
		}
		if(idx == -1) return ret;
		s = t, t = idx, ret = mx, vis[idx] = 1;
		for(int j = 1; j <= n; j++) if(!del[j] && !vis[j]) d[j] += g[idx][j];
	}
	return ret;
}

int global_min_cut(){
	int ret = 1e9;
	for(int i = 1; i < n; i++){
		int s=1, t=1; int now = min_cut(s, t);
		del[t] = 1;
		ret = min(ret, now);
		if(!ret) return 0;
		for(int j = 1; j <= n; j++) if(!del[j]) g[s][j] = (g[j][s] += g[j][t]);
	}
	return ret;
}

int main(){
	cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
	cin >> n >> m; e.resize(n+1);
	for(int i = 1; i <= m; i++){
		int u, v; cin >> u >> v;
		e[u].push_back(v);
		e[v].push_back(u);
		g[u][v] = g[v][u] = 1;
	}
	int sz = n;
	for(int i = 1; i <= n; i++){
		if(!vis[i]) cnt++, sz = min(sz, dfs(i));
	}
	if(sz != n) return !(cout << sz*(n-sz) << '\n' << n*(n-1)/2 - cnt + 2);
	cout << n-1 << '\n' << n*(n-1)/2 - global_min_cut() + 1;
}