ZOJ Monthly, July 2012 - I : Information

問題概要

頂点数n(<100)の有向グラフがある。どれか一つ頂点を選んで取り除き、最大の強連結成分(大きさ2以上)のサイズを最小化する問題。

解法

どれを潰すか全探索して毎回強連結成分分解して間に合う。

acceptされたコード

#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;

const int MAX_V = 100;

int V;
int TABOO;
vector<int> graph[MAX_V];
vector<int> rev_graph[MAX_V];
int cmp[MAX_V];
int cmp_cnt[MAX_V];

namespace StronglyConnectedComponent{
	vector<int> st;
	bool visited[MAX_V];

	void add_edge(int from, int to){
		graph[from].push_back(to);
		rev_graph[to].push_back(from);
	}

	void dfs(int v){
		visited[v] = true;
		if(v!=TABOO)for(int i=0; i<(int)graph[v].size(); ++i){
			const int u = graph[v][i];
			if(u==TABOO) continue;
			if(!visited[u]){
				dfs(u);
			}
		}
		st.push_back(v);
	}

	void rev_dfs(int v, int k){
		visited[v] = true;
		cmp[v] = k;
		if(v!=TABOO)for(int i=0; i<(int)rev_graph[v].size(); ++i){
			const int u = rev_graph[v][i];
			if(u==TABOO) continue;
			if(!visited[u]){
				rev_dfs(u, k);
			}
		}
	}

	int scc(){
		memset(visited, false, sizeof(visited));
		st.clear();
		for(int v=0; v<V; ++v){
			if(!visited[v]){
				dfs(v);
			}
		}
		memset(visited, false, sizeof(visited));
		int k = 0;
		for(;!st.empty();){
			const int v = st.back();
			st.pop_back();
			if(!visited[v]){
				rev_dfs(v, k++);
			}
		}
		return k;
	}
}

using StronglyConnectedComponent::add_edge;
using StronglyConnectedComponent::scc;


int solve() {
	int ans = V;

	for (TABOO = 0; TABOO < V; ++TABOO) {
		scc();
		memset(cmp_cnt, 0, sizeof(cmp_cnt));
		for (int i = 0; i < V; ++i) {
			++cmp_cnt[cmp[i]];
		}
		int maxi = 0;
		for (int i = 0; i < V; ++i) {
			if (cmp_cnt[i] > 1 && cmp_cnt[i] >= maxi) {
				maxi = cmp_cnt[i];
			}
		}
		if (ans > maxi) {
			ans = maxi;
		}
	}

	return ans;
}


bool init() {
	int m;
	if (scanf("%d%d", &V, &m) == EOF) {
		return false;
	}
	for (int i = 0; i < V; ++i) {
		graph[i].clear();
		rev_graph[i].clear();
	}
	for (int _ = 0; _ < m; ++_) {
		int from, to;
		scanf("%d%d", &from, &to);
		add_edge(from, to);
	}
	return true;
}

int main() {
	for (;init();) {
		printf("%d\n", solve());
	}
	return 0;
}