UVA1108 Mining Your Own Business
题意:在一个无向图上选择尽量少的点涂黑,使得删除任意一个点后,每个连通分量里都至少有一个黑点。
分析:对于每一个双连通分量,以割点数量分情况讨论:
-
0个割点:不能与其他双连通分量的黑点连通,因此至少需要设2个黑点,方案为任选其中两个节点。方案数为(frac{sz imes(sz-1)}{2})。
-
1个割点:在删除的点不是割点时,能通过割点与其他双连通分量的黑点连通;当删除的点是割点时,在其内部设1个黑点即可。方案为任选其中一个飞割点。方案数为(sz-1)。
-
2个及以上割点:必能通过割点与其他双连通分量的黑点连通,因此不需要设黑点。
注意双连通分量间的方案数是乘法原理,总方案数是所有方案数相乘。
#define mem(a,n) memset(a,n,sizeof(a))
#define f(i,a,b) for(int i=a;i<=b;i++)
#define af(i,a,b) for(int i=a,i>=b;i--)
#define fe(u,i) for(int i=head[u];i;i=e[i].next)
using namespace std;
typedef long long LL;
const int INF = 20010509;
const int maxn = 2e5 + 100;
const int maxm = 2e5 + 100;
int dfs_clock;
int dfn[maxn], low[maxn];
int head[maxn], cnt = 0;
int n, m;
int iscut[maxn], bccno[maxn], bcc_cnt;
struct Edge {
int from, to, next;
}e[maxm];
stack<Edge> s;
//保留在当前BCC中的边
vector<int> bcc[maxn];
//记录位于bcc[i]上的所有点
void add(int from, int to, Edge eset[], int head[]) {
cnt++;
eset[cnt].from = from;
eset[cnt].to = to;
eset[cnt].next = head[from];
head[from] = cnt;
}
int dfs(int u, int fa) {
low[u] = dfn[u] = ++dfs_clock;
int child = 0;
for (int i = head[u]; i; i = e[i].next) {
int v = e[i].to;
if (!dfn[v]) {
s.push(e[i]);
child++;
low[v] = dfs(v, u);
low[u] = min(low[u], low[v]);
if (low[v] >= dfn[u]) {
iscut[u] = true;
bcc_cnt++; bcc[bcc_cnt].clear();
for (;;) {
Edge x = s.top(); s.pop();
if (bccno[x.from] != bcc_cnt) {
bcc[bcc_cnt].push_back(x.from);
bccno[x.from] = bcc_cnt;
}
if (bccno[x.to] != bcc_cnt) {
bcc[bcc_cnt].push_back(x.to);
bccno[x.to] = bcc_cnt;
}
if (x.from == u && x.to == v) break;
}
}
}
else if (dfn[v] < dfn[u] && v != fa) {
s.push(e[i]);
low[u] = min(low[u], dfn[v]);
}
}
if (fa < 0 && child == 1) iscut[u] = false;
return low[u];
}
void find_bcc() {
dfs_clock = bcc_cnt = 0;
for (int i = 1; i <= n; i++) {
if (!dfn[i]) dfs(i, -1);
}
}
void init() {
mem(e, 0);
mem(head, 0);
cnt = 0;
mem(dfn, 0);
mem(low, 0);
mem(iscut, 0);
mem(bccno, 0);
}
int main(){
int t = 0;
while (cin >> m&& m) {
init();
t++;
f(i, 1, m) {
int u, v;
cin >> u >> v;
add(u, v, e, head);
add(v, u, e, head);
n = max(n, max(u, v));
}
find_bcc();
LL ans1 = 0, ans2 = 1;
f (i, 1, bcc_cnt) {
LL num = 0;
LL sz = bcc[i].size();
for (int j = 0; j < sz; j++) {
if (iscut[bcc[i][j]]) num++;
}
if (num == 0) ans1 += 2, ans2 *= sz * (sz - 1) / 2;
else if (num == 1) ans1 += 1, ans2 *= (sz - 1);
}
cout << "Case " << t << ": " << ans1 << " " << ans2 << endl;
}
return 0;
}