题目链接：http://poj.org/problem?id=2117
题目大意：
给定一个由 \(n\)个点 \(m\) 条边构成的无向图，请你求出该图删除一个点之后，连通块最多有多少。
解题思路：
tarjan，判断 \(u\) 的子节点有几个 \(v\) 满足 \(low[v] \ge dfn[u]\) 就是答案，但是同时如果 \(u\) 不是这个 dfs 树的根节点，个数还要加 \(1\)。
示例程序1（C++11，POJ不支持）：
#include <bits/stdc++.h>
using namespace std;
const int maxn = 10010;
int n, m, dfn[maxn], low[maxn], ts, ans, root;
vector<int> g[maxn];
void init() {
for (int i = 0; i < n; i++) g[i].clear(), dfn[i] = low[i] = 0;
ts = ans = 0;
}
void tarjan(int u, int p) {
dfn[u] = low[u] = ++ts;
int cnt = 0;
for (auto v : g[u]) {
if (v != p) {
if (!dfn[v]) {
tarjan(v, u), low[u] = min(low[u], low[v]);
if (dfn[u] <= low[v])
cnt++;
}
else
low[u] = min(low[u], dfn[v]);
}
}
if (u != root) cnt++;
ans = max(ans, cnt);
}
int main() {
while (~scanf("%d%d", &n, &m) && n) {
init();
for (int i = 0; i < m; i++) {
int u, v;
scanf("%d%d", &u, &v);
g[u].push_back(v);
g[v].push_back(u);
}
int cnt = 0;
for (root = 0; root < n; root++)
if (!dfn[root])
cnt++, tarjan(root, -1);
printf("%d\n", ans + cnt - 1);
}
return 0;
}
示例程序2（POJ支持）：
#include <cstdio>
#include <vector>
#include <iostream>
using namespace std;
const int maxn = 10010;
int n, m, dfn[maxn], low[maxn], ts, ans, root;
vector<int> g[maxn];
void init() {
for (int i = 0; i < n; i++) g[i].clear(), dfn[i] = low[i] = 0;
ts = ans = 0;
}
void tarjan(int u, int p) {
dfn[u] = low[u] = ++ts;
int cnt = 0;
int sz = g[u].size();
for (int i = 0; i < sz; i++) {
int v = g[u][i];
if (v != p) {
if (!dfn[v]) {
tarjan(v, u), low[u] = min(low[u], low[v]);
if (dfn[u] <= low[v])
cnt++;
}
else
low[u] = min(low[u], dfn[v]);
}
}
if (u != root) cnt++;
ans = max(ans, cnt);
}
int main() {
while (~scanf("%d%d", &n, &m) && n) {
init();
for (int i = 0; i < m; i++) {
int u, v;
scanf("%d%d", &u, &v);
g[u].push_back(v);
g[v].push_back(u);
}
int cnt = 0;
for (root = 0; root < n; root++)
if (!dfn[root])
cnt++, tarjan(root, -1);
printf("%d\n", ans + cnt - 1);
}
return 0;
}