出口数量必须 >= 2
分别讨论每个联通块当中割点的数量
如果没有割点, 任取连通分量中的两个点作为出口
如果有割点, 割点数量 == 1, 在连通块中选取除了割点以外的任意一点作为出口, 割点当一个出口
如果割点数量 > 1, 那么不需要出口
#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
typedef unsigned long long LL;
const int NUMBER = 1010, EDGE_NUMBER = 1010;
int number, edge_number;
int head[NUMBER], edge_end[EDGE_NUMBER], next_edge[EDGE_NUMBER], edge_index;
int dfn[NUMBER], low[NUMBER], timestamp;
int stack[NUMBER], top, dcc_cnt;
bool is_cut[NUMBER];
vector<int> dcc[NUMBER];
int root;
void add_edge(int start, int end) {
edge_end[edge_index] = end, next_edge[edge_index] = head[start], head[start] = edge_index++;
}
void tarjan(int _node) {
dfn[_node] = low[_node] = ++timestamp;
stack[++top] = _node;
// 当前点是孤立点
if (_node == root && head[_node] == -1) {
dcc_cnt++;
dcc[dcc_cnt].push_back(_node);
return;
}
// 统计当前点下面的dcc数量, 如果dcc数量 <= 1, 那么不能是割点
int cnt = 0;
for (int i = head[_node]; ~i; i = next_edge[i]) {
int ver = edge_end[i];
if (!dfn[ver]) {
tarjan(ver);
low[_node] = min(low[_node], low[ver]);
if (dfn[_node] <= low[ver]) {
cnt++;
if (_node != root || cnt > 1) is_cut[_node] = true;
++dcc_cnt;
int val;
do {
val = stack[top--];
dcc[dcc_cnt].push_back(val);
} while (val != ver);
// 将当前割点也加入到dcc中
dcc[dcc_cnt].push_back(_node);
}
}
else low[_node] = min(low[_node], dfn[ver]);
}
}
int main() {
int cases = 1;
while (scanf("%d", &edge_number), edge_number) {
for (int i = 1; i <= dcc_cnt; ++i) dcc[i].clear();
memset(head, -1, sizeof head);
memset(dfn, 0, sizeof dfn);
memset(is_cut, false, sizeof is_cut);
edge_index = number = timestamp = top = dcc_cnt = 0;
while (edge_number--) {
int ver1, ver2;
scanf("%d%d", &ver1, &ver2);
add_edge(ver1, ver2);
add_edge(ver2, ver1);
int val = max(ver1, ver2);
number = max(number, val);
}
for (root = 1; root <= number; ++root) {
if (!dfn[root]) tarjan(root);
}
int res = 0;
LL sum = 1;
for (int i = 1; i <= dcc_cnt; ++i) {
int cnt = 0;
for (int j = 0; j < dcc[i].size(); ++j) {
if (is_cut[dcc[i][j]]) cnt++;
}
if (cnt == 0) {
if (dcc[i].size() > 1) {
res += 2;
sum *= dcc[i].size() * (dcc[i].size() - 1) / 2;
}
else res++;
}
else if (cnt == 1) res++, sum *= dcc[i].size() - 1;
}
printf("Case %d: %d %llu\n", cases++, res, sum);
}
return 0;
}