思路与算法

对每个无向连通分量做迭代Tarjan，记录tin、low、DFS父亲。非根删除后保留父亲方向1块，每个low[child]≥tin[u]的孩子再贡献1块；根删除后块数就是DFS孩子数。若原图有cc块，则删u后的总块数为cc-1+局部分块数，取最大。图用64位位矩阵保存，不假设未公布的小边数上限。

正确性说明

子树low能回到u之前的祖先时，删除u后仍连接父亲方向；不能回去的子树恰好独立成一块。不同DFS孩子之间没有绕开u的连接，否则会被同一DFS子树覆盖。根没有父亲方向，要单独从0计数。其他原连通分量不受删除影响，因此加cc-1，孤立点删除使自己的分量消失，也被同一公式正确处理。

复杂度

位矩阵空间O(P²/64)，其余O(P)。逐顶点扫描所有邻接位的时间O(P²+C)，输入读取O(C)，矩阵及数组初始化也已计入。P≤10000，位矩阵约12.6MB，支持无重边图的完整可能边数；显式栈避免1万深链的调用栈限制。

易错点

不能假设图原本连通。根的初始局部块数为0，非根为1。P=1删点后答案0；全孤立图答案P-1。输入0终止，样例使用0 0也可读取。独立答案逐个删除顶点后重新搜索计数，满规模路径/星形/空图用结构公式。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    while (cin >> n && n) {
        long long m;
        cin >> m;
        int words = (n + 63) / 64;
        vector<unsigned long long> a(size_t(n) * words);
        for (long long i = 0; i < m; ++i) {
            int u, v;
            cin >> u >> v;
            a[size_t(u) * words + v / 64] |= 1ULL << (v % 64);
            a[size_t(v) * words + u / 64] |= 1ULL << (u % 64);
        }
        vector<int> tin(n), low(n), parent(n, -1), next(n), parts(n, 1), stack;
        int timer = 0, components = 0;
        for (int root = 0; root < n; ++root)
            if (!tin[root]) {
                ++components;
                parts[root] = 0;
                tin[root] = low[root] = ++timer;
                stack.push_back(root);
                while (!stack.empty()) {
                    int u = stack.back();
                    int v = next[u];
                    while (v < n && !(a[size_t(u) * words + v / 64] >> (v % 64) & 1ULL))
                        ++v;
                    next[u] = v + 1;
                    if (v == n) {
                        stack.pop_back();
                        int p = parent[u];
                        if (p >= 0) {
                            low[p] = min(low[p], low[u]);
                            if (low[u] >= tin[p])
                                ++parts[p];
                        }
                    } else if (!tin[v]) {
                        parent[v] = u;
                        tin[v] = low[v] = ++timer;
                        stack.push_back(v);
                    } else if (v != parent[u])
                        low[u] = min(low[u], tin[v]);
                }
            }
        int answer = 0;
        for (int x : parts)
            answer = max(answer, components - 1 + x);
        cout << answer << '\n';
    }
}