POJ 3713: Transferring Sylla

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の定理を使っているからフローの考えを使うといえなくもないけど…