「HNOI2012」矿场搭建

煤矿工地可以看成是由隧道连接挖煤点组成的无向图。为安全起见，希望在工地发生事故时所有挖煤点的工人都能有一条出路逃到救援出口处。于是矿主决定在某些挖煤点设立救援出口，使得无论哪一个挖煤点坍塌之后，其他挖煤点的工人都有一条道路通向救援出口。

请写一个程序，用来计算至少需要设置几个救援出口，以及不同最少救援出口的设置方案总数。

链接

LOJ 10099

Luogu 3225

题解

Tarjan 算法求点双连通分量。

当求得一个割点时，子树所有节点出栈并标记为一个点双连通分量，由于割点可能属于多个点双连通分量，所以割点也被标记为同一个点双连通分量，但是不出栈。

如果原图就是一个点双连通分量，那么设置任意两个出口，就可以保证破坏掉任意一个点后，至少有一个出口。

如果点双连通分量有一个割点，在这个点双连通分量中设置任意一个非割点出口。那么破坏割点，还有出口；破坏出口，这可以从割点连到其它点双连通分量。

如果点双连通分量有两个或两个以上的割点，不用设置出口，可以保证破坏掉任意一个点后，至少有一个割点，可以通过它连到其它点双连通分量。

乘法原理统计即可。

代码

#include <cstdio>
#include <cstring>
#include <vector>

using std::vector;

typedef long long ll;

const int SIZE = 10005;

int cut[SIZE], bccTot, root;
int low[SIZE], dfn[SIZE], time;
int st[SIZE], top;
int h[SIZE], to[SIZE << 1], nxt[SIZE << 1], tot;
vector<int> bccList[SIZE];

int min(int x, int y) {
	return x < y ? x : y;
}

int max(int x, int y) {
	return x > y ? x : y;
}

void add(int x, int y) {
	to[++tot] = y;
	nxt[tot] = h[x];
	h[x] = tot;
}

void tarjan(int x) {
	low[x] = dfn[x] = ++time;
	int cnt = 0;
	st[++top] = x;
	for (int i = h[x]; i; i = nxt[i]) {
		int y = to[i];
		if (!dfn[y]) {
			cnt++;
			tarjan(y);
			low[x] = min(low[x], low[y]);
			if (x == root && cnt >= 2) {
				cut[x] = 1;
			} else if (x != root && dfn[x] <= low[y]) {
				cut[x] = 1;
			}
			if (dfn[x] <= low[y]) {
				++bccTot;
				bccList[bccTot].clear();
				bccList[bccTot].push_back(st[top--]);
				while (st[top+1] != y) {
					bccList[bccTot].push_back(st[top--]);
				}
				bccList[bccTot].push_back(st[top]);
			}
		}
		else low[x] = min(low[x], dfn[y]);
	}
}

void init() {
	time = 0, top = 0;
	tot = 0, bccTot = 0;
	memset(h, 0, sizeof(h));
	memset(dfn, 0, sizeof(dfn));
	memset(cut, 0, sizeof(cut));
}

int main() {
	int n, m;
	int T = 1;
	while (scanf("%d", &m) && m) {
		n = 0;
		init();
		for (int i = 1; i <= m; i++) {
			int x, y;
			scanf("%d %d", &x, &y);
			n = max(n, max(x, y));
			add(x, y);
			add(y, x);
		}
		for (int i = 1; i <= n; i++) if (!dfn[i]) root = i, tarjan(i);
		ll res = 0, num = 1;
		for (int i = 1; i <= bccTot; i++) {
			ll cnt = 0, len = bccList[i].size();
			for (int j = 0; j < len; j++) {
				if (cut[bccList[i][j]]) cnt++;
			}
			if (cnt == 0) res += 2, num = (num * len * (len - 1)) >> 1;
			else if (cnt == 1) res += 1, num = (num * (len - 1));
			else if (cnt >= 2) continue;
		}
		printf("Case %d: %lld %lld
", T++, res, num);
	}
	return 0;
}