POJ-3713 : Transferring Sylla

問題概要

頂点数V(<500)の無向グラフが与えられる。任意の2点間に点素パスが3本以上存在するかどうか判定する問題。

解法

最初は最大流だから全域最小カットだとおもったけど違う。メンガーの定理より、求めるものは最小点カットが3以上かどうかだが、普段使っている最小カットは最小辺カットで、これは最小点カットではない。最小点カットが2以上であるかどうかは関節点の存在を調べることによって判定できるので、どの1点を消すか全探索して関節点が存在するかを調べればよい。
定数倍が厳しいので頑張って高速化する。

acceptされたコード

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

const int MAX_N = 500;

int N, M, R;
int G[MAX_N][MAX_N], rev[MAX_N][MAX_N];
bool used[MAX_N][MAX_N];
int usedCount;
pair<int,int> usedEdge[MAX_N*MAX_N];
int order[MAX_N], lowlink[MAX_N], degs[MAX_N];
bool visited[MAX_N];

void addUndirectedEdge(int from, int to) {
	rev[from][degs[from]] = degs[to];
	G[from][degs[from]] = to;
	rev[to][degs[to]] = degs[from]++;
	G[to][degs[to]++] = from;
}

bool dfs(int v, int &k) {
	visited[v] = true;
	order[v] = k++;
	lowlink[v] = order[v];
	int cnt = 0;
	for (int i = 0; i < degs[v]; ++i) {
		const int u = G[v][i];
		if (u == R) {
			continue;
		}
		if (!visited[u]) {
			++cnt;
			used[v][i] = true;
			usedEdge[usedCount++] = make_pair(v, i);
			if(dfs(u, k) || (v != (R==0?1:0) && order[v] <= lowlink[u])) return true;
			lowlink[v] = min( lowlink[v], lowlink[u] );
		}
		else if (!used[u][rev[v][i]]) {
			lowlink[v] = min( lowlink[v], order[u] );
		}
	}
	if (v == (R==0?1:0) && cnt > 1) {
		return true;
	}
	return false;
}

bool findArticulation() {
	memset(visited, false, sizeof(visited));
	int k = 0;

	for (int v = 0; v < N; ++v) if (v != R && !visited[v]) {
		if (v != (R==0 ? 1 : 0) || dfs(v, k)) {
			return true;
		}
	}
	return false;
}

bool init() {
	scanf("%d%d", &N, &M);
	memset(degs, 0, sizeof(degs));
	for (int _ = 0; _ < M; ++_) {
		int from, to;
		scanf("%d%d", &from, &to);
		addUndirectedEdge(from, to);
	}
	return N > 0;
}

bool solve() {
	if (N < 4) {
		return false;
	}
	for (R = 0; R < N; ++R) {
		for (int i = 0; i < usedCount; ++i) {
			used[usedEdge[i].first][usedEdge[i].second] = false;
		}
		usedCount = 0;
		if(findArticulation()) {
			return false;
		}
	}
	return true;
}

int main() {
	for (;init();) {
		puts(solve() ? "YES" : "NO");
	}
	return 0;
}