Mengerの定理より全域最小点カットを求めれば良い。
すべての点対に対してフローを流せばできるが、それではTLE。
全域最小辺カットならO(V^3)のアルゴリズム(Stoer-Wagner)が存在するが、全域最小点カットは見つけられなかった。
全域最小点カットが2以上になるかは関節点が存在しないことに言い換えられるので、
3以上になるかはどの1点を消しても関節点が存在しないことと同値。
3という数字が絶妙。4以上だったらフローの方が速い。
int N, M; vector<int> G[MAX_N]; bool used[MAX_N]; int low[MAX_N], ord[MAX_N]; void lowlink(int at, int p, int &k, int ng) { //int &k can be altered as int k //used this as lowlink(0, -1, k). declare int k = 0 //if(ord[at] < low[n]) (n, at) is a bridge //if(at == 0) if(nG[at].size() > 1) at is an articulation point //else if(ord[at] <= low[n]) at is an articulation point used[at] = true; low[at] = ord[at] = k; k++; for(int i = 0; i < G[at].size(); i++) { int n = G[at][i]; if(!used[n] && n != ng) { lowlink(n, at, k, ng); low[at] = min(low[at], low[n]); } else if(n != p && n != ng) low[at] = min(low[at], ord[n]); } } int dfs(int at, int root, int ng) { used[at] = true; bool tmp = false; int cnt = 0, res = 0; for(int i = 0; i < G[at].size(); i++) { int n = G[at][i]; if(used[n] || n == ng) continue; if(at != root && ord[at] <= low[n] && !tmp) { res++; tmp = true; } res += dfs(n, root, ng); cnt++; } if(at == root && cnt > 1) { res++; } return res; } int main() { while(true) { scanf("%d%d", &N, &M); if(N == 0 && M == 0) break; rep(i, 0, N) G[i].clear(); rep(i, 0, M) { int a, b; scanf("%d%d", &a, &b); G[a].push_back(b); G[b].push_back(a); } bool found = false; rep(i, 0, N) { memset(low, 0, sizeof(low)); memset(used, 0, sizeof(used)); memset(ord, 0, sizeof(ord)); int k = 0; if(i != 0) { lowlink(0, -1, k, i); memset(used, 0, sizeof(used)); int a = dfs(0, 0, i); if(a) { found = true; break; } } else { lowlink(1, -1, k, i); memset(used, 0, sizeof(used)); int a = dfs(1, 1, i); if(a) { found = true; break; } } rep(j, 0, N) { if(j != i && !used[j]) { found = true; break; } } if(found) break; } if(found) printf("NO\n"); else printf("YES\n"); } return 0; }
Mengerの定理を使っているからフローの考えを使うといえなくもないけど…