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; }