刘汝佳白书上面的一道题目：题意是给定一个联通分量，求出割顶以及双连通分量的个数，并且要求出安放安全井的种类数，也就是每个双连通分量中结点数（除开 割顶）个数相乘，对于有2个及以上割顶的双连通分量可以不用安放安全井。如果整个图就是一个双连通分量，那么需要安放两个安全井，种类数是n*(n-1)/2.
代码来自刘汝佳白书：
#include <iostream>
#include <sstream>
#include <cstdio>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <string>
#include <stack>
#include <map>
#include <cmath>
#include <vector>
#include <queue>
#include <algorithm>
#define esp 1e-6
#define pi acos(-1.0)
#define pb push_back
#define mp(a, b) make_pair((a), (b))
#define in freopen("in.txt", "r", stdin);
#define out freopen("out.txt", "w", stdout);
#define print(a) printf("%d\n",(a));
#define bug puts("********))))))");
#define stop system("pause");
#define Rep(i, c) for(__typeof(c.end()) i = c.begin(); i != c.end(); i++)
#define pragma comment(linker, "/STACK:102400000, 102400000")
#define inf 0x0f0f0f0f using namespace std;
typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> pii;
typedef vector<pii,int> VII;
typedef vector<int>:: iterator IT;
const int maxn = ;
struct Edge{
int u, v;
Edge(int u, int v):u(u), v(v){}
};
int pre[maxn], low[maxn], bccno[maxn], iscut[maxn], bcc_cnt, dfs_clock;
VI g[maxn], bcc[maxn];
stack<Edge> S;
int dfs(int u, int fa)
{
int lowu = pre[u] = ++dfs_clock;
int child = ;
for(int i = ; i < g[u].size(); i++)
{
int v = g[u][i]; Edge e = Edge(u, v);
if(!pre[v])
{
S.push(e);
child++;
int lowv = dfs(v, u);
lowu = min(lowu, lowv);
if(lowv >= pre[u])
{
iscut[u] = ;
bcc_cnt++; bcc[bcc_cnt].clear();
for(;;)
{
Edge x = S.top(); S.pop();
if(bccno[x.u] != bcc_cnt) {bccno[x.u] = bcc_cnt; bcc[bcc_cnt].pb(x.u);}
if(bccno[x.v] != bcc_cnt) {bccno[x.v] = bcc_cnt; bcc[bcc_cnt].pb(x.v);}
if(x.u == u && x.v == v) break;
}
}
}
else if(pre[v] < pre[u] && v!= fa)
{
S.push(e);
lowu = min(lowu, pre[v]);
}
}
if(child == && fa < ) iscut[u] = ;
return low[u] = lowu;
}
void find_bcc(int n)
{
memset(iscut, , sizeof(iscut));
memset(pre, , sizeof(pre));
memset(bccno, , sizeof(bccno)); dfs_clock = bcc_cnt = ;
for(int i = ; i < n; i++)
if(!pre[i]) dfs(i, -);
}
int kase;
void solve(int n)
{
find_bcc(n);
LL ans1 = , ans2 = ;
for(int i = ; i <= bcc_cnt; i++)
{
int cut_cnt = ;
for(int j = ; j < bcc[i].size(); j++)
if(iscut[bcc[i][j]]) cut_cnt++;
if(cut_cnt == )
ans1++, ans2 *= (LL)(bcc[i].size() - cut_cnt);
}
if(bcc_cnt == )
{
ans1 = , ans2 = (LL)(n-)*n/;
}
printf("Case %d: %I64d %I64d\n", kase, ans1, ans2);
}
int main(void)
{
int m;
while(scanf("%d", &m), m)
{
kase++;
for(int i = ; i < maxn; i++)
g[i].clear();
int mxn = ;
while(m--)
{
int u, v;
scanf("%d%d", &u, &v);
mxn = max(mxn, max(u, v));
u--, v--;
g[u].pb(v), g[v].pb(u);
}
solve(mxn);
}
return ;
}
此题的另一种解法是先求出割顶，然后从非割顶的点dfs一遍，注意这个过程中不能经过割顶，统计每次dfs中遇到割顶的数目，如果为1，则更新答案。同样注意割顶为0的情况。
代码：
#include <iostream>
#include <sstream>
#include <cstdio>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <string>
#include <stack>
#include <map>
#include <cmath>
#include <vector>
#include <queue>
#include <algorithm>
#define esp 1e-6
#define pi acos(-1.0)
#define pb push_back
#define mp(a, b) make_pair((a), (b))
#define in freopen("in.txt", "r", stdin);
#define out freopen("out.txt", "w", stdout);
#define print(a) printf("%d\n",(a));
#define bug puts("********))))))");
#define stop system("pause");
#define Rep(i, c) for(__typeof(c.end()) i = c.begin(); i != c.end(); i++)
#define inf 0x0f0f0f0f
#pragma comment(linker, "/STACK:102400000,102400000") using namespace std;
typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> pii;
typedef vector<pii,int> VII;
typedef vector<int>:: iterator IT;
const int maxn = + ;
int pre[maxn], low[maxn], iscut[maxn], dfs_clock;
VI g[maxn], cut;
int n;
LL ans1, ans2, cut_cnt;
int dfs(int u, int fa)
{
int lowu = pre[u] = ++dfs_clock;
int child = ;
for(int i = ; i < g[u].size(); i++)
{
int v = g[u][i];
if(!pre[v])
{
child++;
int lowv = dfs(v, u);
lowu = min(lowu, lowv);
if(lowv >= pre[u])
{
iscut[u] = ;
}
}
else if(pre[v] < pre[u] && v != fa)
{
lowu = min(lowu, pre[v]);
}
}
if(child == && fa < )
iscut[u] = ;
return low[u] = lowu;
}
void find_bcc(int n)
{
memset(pre, , sizeof(pre));
memset(iscut, , sizeof(iscut));
dfs_clock = ;
for(int i = ; i < n; i++)
if(!pre[i])
dfs(i, -);
}
int cnt;
void dfs1(int u)
{
cnt++;
pre[u] = ;
for(int i = ; i < g[u].size(); i++)
{
int v = g[u][i];
if(!pre[v])
{
if(iscut[v]) cut_cnt++, cnt++, pre[v] = , cut.pb(v);
else dfs1(v);
}
}
}
void solve(int n)
{
cut.clear();
cut_cnt= ;
memset(pre, , sizeof(pre));
for(int i = ; i < n; i++)
if(iscut[i]) cut_cnt++; if(cut_cnt == ) ans1 = , ans2 = (LL)n*(n-)/;
else for(int i = ; i < n; i++)
if(!pre[i] && !iscut[i])
{
cut_cnt = cnt = ;
dfs1(i);
for(int i = ; i < cut.size(); i++)
pre[cut[i]] = ;
cut.clear();
if(cut_cnt == )
ans1++, ans2 *= (LL)(cnt-);
}
}
int main(void)
{
int m, t = ;
while(scanf("%d", &m), m)
{
n = ;
ans1 = , ans2 = ;
for(int i = ; i < maxn; i++)
g[i].clear();
while(m--)
{
int u, v;
scanf("%d%d", &u, &v);
n = max(n, max(u, v));
u--, v--;
g[u].pb(v);
g[v].pb(u);
}
find_bcc(n);
solve(n);
printf("Case %d: %I64d %I64d\n", t, ans1, ans2);
t++;
}
return ;
}