传送
翻译一下,就是:在一个无向图上选择尽量少的点涂黑,使得任意删除一个点后,每个联通分量至少有一个黑点。
那自然会想到先求v-DCC。
然后咧?
对于每一个v-DCC:
1.如果只有一个割点,就选不是割点的任意一个点染色。
2.大于一个割点,不用染色。
因为如果只有一个割点,删除后这个v-DCC中的点就走不出去了,所以要在里面选一个染色。
如果有多个割点,删除一个割点后其他点都可以走出去到别的v-DCC中,就不用染色了。
其实就是把新图(准确说是树)中的叶子节点染色。
需要注意的是,如果整张图没有割点,那答案是\(C_{n}^{2}\)。
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<vector>
#include<queue>
#include<assert.h>
#include<ctime>
using namespace std;
#define enter puts("")
#define space putchar(' ')
#define Mem(a, x) memset(a, x, sizeof(a))
#define In inline
#define forE(i, x, y) for(int i = head[x], y; ~i && (y = e[i].to); i = e[i].nxt)
typedef long long ll;
typedef double db;
const int INF = 0x3f3f3f3f;
const db eps = 1e-8;
const int maxn = 1e5 + 5;
In ll read()
{
ll ans = 0;
char ch = getchar(), las = ' ';
while(!isdigit(ch)) las = ch, ch = getchar();
while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar();
if(las == '-') ans = -ans;
return ans;
}
In void write(ll x)
{
if(x < 0) x = -x, putchar('-');
if(x >= 10) write(x / 10);
putchar(x % 10 + '0');
}
In void MYFILE()
{
#ifndef mrclr
freopen(".in", "r", stdin);
freopen(".out", "w", stdout);
#endif
}
int n, m;
struct Edge
{
int nxt, to;
}e[maxn << 1];
int head[maxn], ecnt = -1;
In void addEdge(int x, int y)
{
e[++ecnt] = (Edge){head[x], y};
head[x] = ecnt;
}
int dfn[maxn], low[maxn], cnt = 0;
int st[maxn], top = 0;
vector<int> dcc[maxn];
int root, cut[maxn], ccol = 0;
In void tarjan(int now)
{
dfn[now] = low[now] = ++cnt;
st[++top] = now;
int flg = 0;
forE(i, now, v)
{
if(!dfn[v])
{
tarjan(v);
low[now] = min(low[now], low[v]);
if(low[v] >= dfn[now])
{
++flg;
if(now != root || flg > 1) cut[now] = 1;
int x; dcc[++ccol].clear();
do
{
x = st[top--];
dcc[ccol].push_back(x);
}while(x ^ v);
dcc[ccol].push_back(now);
}
}
else low[now] = min(low[now], dfn[v]);
}
}
In void init()
{
n = 0;
Mem(head, -1), ecnt = -1;
cnt = top = ccol = 0;
Mem(dfn, 0), Mem(low, 0), Mem(cut, 0);
}
int main()
{
// MYFILE();
int T = 0;
while(scanf("%d", &m) && m)
{
init();
for(int i = 1; i <= m; ++i)
{
int x = read(), y = read();
n = max(n, max(x, y));
addEdge(x, y), addEdge(y, x);
}
for(int i = 1; i <= n; ++i) if(!dfn[i]) root = i, tarjan(i);
ll ans1 = 0, ans2 = 1;
if(ccol == 1) ans1 = 2, ans2 = 1LL * n * (n - 1) / 2;
else
{
for(int i = 1; i <= ccol; ++i)
{
int num = 0, siz = dcc[i].size();
for(int j = 0; j < siz; ++j) num += cut[dcc[i][j]];
if(num == 1) ++ans1, ans2 *= 1LL * (siz - num);
}
}
printf("Case %d: %lld %lld\n", ++T, ans1, ans2);
}
return 0;
}