|
|
|
|
|
#include <bits/stdc++.h>
|
|
|
|
|
|
using namespace std;
|
|
|
|
|
|
typedef long long LL;
|
|
|
|
|
|
const int N = 1010, M = N << 2;
|
|
|
|
|
|
int n, m;
|
|
|
|
|
|
|
|
|
|
|
|
// 链式前向星
|
|
|
|
|
|
int e[M], h[N], idx, w[M], ne[M];
|
|
|
|
|
|
void add(int a, int b, int c = 0) {
|
|
|
|
|
|
e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
|
|
|
|
|
|
}
|
|
|
|
|
|
/*
|
|
|
|
|
|
1. 用tarjan跑出所有的v_bcc和 原图中哪些点是割点
|
|
|
|
|
|
2. 遍历每个v_bcc(点双),考查点双里的割点个数：
|
|
|
|
|
|
(1). 若此点双内包含的割点数>1，则无论哪一个节点被毁，连通性依旧,不用处理。贡献为0
|
|
|
|
|
|
(2). 若此点双内包含的割点数=1，则在分量内任意一点建一个(割点处不用建)，一旦分量内建立好的救援出口被毁，
|
|
|
|
|
|
可以通过割点跑到相临的分量中，走别人的救援出口，ans*=bcc.size()-1。贡献为1
|
|
|
|
|
|
(3). 若此点双内包含的割点数=0，则任建两个，ans=bcc.size()(bcc.size()-1)/2。贡献为2
|
|
|
|
|
|
*/
|
|
|
|
|
|
int dfn[N], low[N], stk[N], ts, top, root;
|
|
|
|
|
|
int bcnt;
|
|
|
|
|
|
vector<int> bcc[N]; // 双连通分量
|
|
|
|
|
|
bool cut[N]; // 记录割点的桶,割点可能会重复，所以用桶来记录，最后用循环来统计
|
|
|
|
|
|
void tarjan(int u, int fa) {
|
|
|
|
|
|
low[u] = dfn[u] = ++ts;
|
|
|
|
|
|
stk[++top] = u;
|
|
|
|
|
|
int son = 0; // 求割点时，需要记录点双中节点的数量，用于判断是不是单个节点组成的
|
|
|
|
|
|
for (int i = h[u]; ~i; i = ne[i]) {
|
|
|
|
|
|
int v = e[i];
|
|
|
|
|
|
if (v == fa) continue;
|
|
|
|
|
|
if (!dfn[v]) {
|
|
|
|
|
|
son++;
|
|
|
|
|
|
tarjan(v, u);
|
|
|
|
|
|
low[u] = min(low[u], low[v]);
|
|
|
|
|
|
|
|
|
|
|
|
// 总结：需要孩子仔细理解原理，能清晰的讲解原理，并默写画出原理图，才能把代码写明白，不能靠简单的背代码，会记不住的
|
|
|
|
|
|
// 原理 : https://www.cnblogs.com/littlehb/p/16091406.html
|
|
|
|
|
|
if (low[v] >= dfn[u]) {
|
|
|
|
|
|
int x;
|
|
|
|
|
|
// 记录割点
|
|
|
|
|
|
if (u != root) cut[u] = 1;
|
|
|
|
|
|
if (u == root && son >= 2) cut[u] = 1; // 如果u是根节点，但是它至少有两个子节点：则u是割点
|
|
|
|
|
|
// 如果u是根，并且有1个子节点，那么去掉u后，剩下的那个节点还是双点，所以，u不是割点
|
|
|
|
|
|
|
|
|
|
|
|
// 记录点双中节点有哪些
|
|
|
|
|
|
bcnt++;
|
|
|
|
|
|
do {
|
|
|
|
|
|
x = stk[top--];
|
|
|
|
|
|
bcc[bcnt].push_back(x);
|
|
|
|
|
|
} while (x != v); // 将子树出栈
|
|
|
|
|
|
bcc[bcnt].push_back(u); // 把割点/树根也丢到点双里
|
|
|
|
|
|
}
|
|
|
|
|
|
} else
|
|
|
|
|
|
low[u] = min(low[u], dfn[v]);
|
|
|
|
|
|
}
|
|
|
|
|
|
// 因为上面枚举的是边，如果是一个孤立的根，是没有边的，上面的代码不会执行，但它确实是一个点双
|
|
|
|
|
|
if (u == root && son == 0) bcc[++bcnt].push_back(u);
|
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
|
|
int main() {
|
|
|
|
|
|
int T = 1;
|
|
|
|
|
|
while (scanf("%d", &m), m) {
|
|
|
|
|
|
// 每次清除上次记录的bcnt连通块中点的向量数组
|
|
|
|
|
|
for (int i = 1; i <= bcnt; i++) bcc[i].clear();
|
|
|
|
|
|
|
|
|
|
|
|
// n:这题太讨厌了，n居然让我们自己取max计算出来，shit~
|
|
|
|
|
|
idx = n = ts = top = bcnt = 0;
|
|
|
|
|
|
memset(h, -1, sizeof h); // 初始化链式前向星
|
|
|
|
|
|
memset(dfn, 0, sizeof dfn); // 每个节点的dfs序时间戳
|
|
|
|
|
|
memset(low, 0, sizeof low);
|
|
|
|
|
|
memset(stk, 0, sizeof stk); // 栈
|
|
|
|
|
|
memset(cut, 0, sizeof cut); // 清空割点数组
|
|
|
|
|
|
|
|
|
|
|
|
while (m--) {
|
|
|
|
|
|
int a, b;
|
|
|
|
|
|
scanf("%d %d", &a, &b);
|
|
|
|
|
|
n = max(n, a), n = max(n, b); // 鄙视一下~
|
|
|
|
|
|
if (a != b) add(a, b), add(b, a);
|
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
|
|
for (root = 1; root <= n; root++)
|
|
|
|
|
|
if (!dfn[root]) tarjan(root, -1); // 以root为根开始找出 割点 和 点双
|
|
|
|
|
|
|
|
|
|
|
|
int res = 0; // 增加的救援出口个数
|
|
|
|
|
|
LL num = 1; // 增加的救援出口方案数
|
|
|
|
|
|
|
|
|
|
|
|
for (int i = 1; i <= bcnt; i++) { // 枚举每个点双
|
|
|
|
|
|
int cnt = 0; // 此点双中割点的数量
|
|
|
|
|
|
for (int j = 0; j < bcc[i].size(); j++) // 枚举点双中每个点，通过cut这个桶判断是不是割点
|
|
|
|
|
|
if (cut[bcc[i][j]]) cnt++;
|
|
|
|
|
|
|
|
|
|
|
|
if (cnt == 0) { // 如果没有割点
|
|
|
|
|
|
// 如果点双中点的数量大于1，救援出口需要在bcc[i].size()中选择两个,一个坏了还可以走另一个
|
|
|
|
|
|
if (bcc[i].size() > 1)
|
|
|
|
|
|
res += 2, num *= bcc[i].size() * (bcc[i].size() - 1) / 2;
|
|
|
|
|
|
else
|
|
|
|
|
|
// 如果点双中点的数量等于1,孤立的点，那么必须单独设立一个救援出口方案数量不用变化
|
|
|
|
|
|
res++;
|
|
|
|
|
|
} else if (cnt == 1) // 如果有一个割点
|
|
|
|
|
|
res++, num *= bcc[i].size() - 1; // 需要添加一个救援出口
|
|
|
|
|
|
// 如果有2个或以上的割点，就不用管了，因为一旦某个割点被毁，可以走另一个
|
|
|
|
|
|
}
|
|
|
|
|
|
printf("Case %d: %d %lld\n", T++, res, num); // 救援出口个数，方案数
|
|
|
|
|
|
}
|
|
|
|
|
|
return 0;
|
|
|
|
|
|
}
|
