python/TangDou/AcWing/DCC/1183.md

AcWing 1183 电力

一、题目描述

给定一个由 n 个点 m 条边构成的 无向图 ，请你求出该图 删除一个点 之后，连通块最多有多少。

输入格式 输入包含多组数据。

每组数据第一行包含两个整数 n,m。

接下来 m 行，每行包含两个整数 a,b，表示 a,b 两点之间有边连接。

数据保证无重边。

点的编号从 0 到 n−1。

读入以一行 0 0 结束。

输出格式 每组数据输出一个结果，占一行，表示连通块的最大数量。

数据范围 1≤n≤10000,0≤m≤15000,0≤a,b<n

输入样例：

3 3
0 1
0 2
2 1
4 2
0 1
2 3
3 1
1 0
0 0

输出样例：

1
2
2

二、解题思路

每个连通块内找下是否存在 割点,如果存在割点，尝试 删除它后会产生多少个新的连通块数S

注意: 在通过割点求连通块时，需要 特判根节点，不是根节点，还需要加上通往根节点那条边指向的连通块，即S+1

• 原来有cnt个，现在你删除一个割点导致增加了2个独立块的话，其实是1->2,需要把原来的1再去掉，即cnt+S-1就是答案

三、实现代码

#include <bits/stdc++.h>
using namespace std;

const int N = 100010, M = 300010;

// 链式前向星
int e[M], h[N], idx, w[M], ne[M];
void add(int a, int b, int c = 0) {
    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}

// 点双连通分量
int dfn[N], low[N], stk[N], ts, top, root;
vector<int> bcc[N];
int bcnt;
void tarjan(int u, int fa) {
    int cnt = 0; // 去掉u之后还剩多少个连通块

    low[u] = dfn[u] = ++ts;
    stk[++top] = u;
    int son = 0;
    for (int i = h[u]; ~i; i = ne[i]) {
        int v = e[i];
        if (v == fa) continue;
        if (!dfn[v]) {
            son++;
            tarjan(v, u);
            low[u] = min(low[u], low[v]);

            if (low[v] >= dfn[u]) {
                cnt++; // u是割点，把u删除掉，所有的v就都孤立了，多出来1个孤立块v

                int x;
                bcnt++;
                do {
                    x = stk[top--];
                    bcc[bcnt].push_back(x);
                } while (x != v);       // 将子树出栈
                bcc[bcnt].push_back(u); // 把割点/树根也丢到点双里
            }
        }
        low[u] = min(low[u], dfn[v]);
    }

    if (fa == -1 && son == 0) bcc[++bcnt].push_back(u); // 特判独立点,单独成点双,本题可以不用管这个
    if (u != root) cnt++;                               // u不是根节点的话，除了自己的子树，还有他的父节点也断开了连接
    ans = max(ans, cnt);                                // 不断更新生成的孤立块最大数量
}

int ans; // 在处理每个连通块时，尝试删除每一个割点，记录可以生成的孤立块的数量最大值

int main() {
    int n, m;
    while (scanf("%d %d", &n, &m), n || m) {
        memset(dfn, 0, sizeof dfn);
        memset(low, 0, sizeof low);
        memset(stk, 0, sizeof stk);
        memset(h, -1, sizeof h);
        idx = ts = top = 0;

        while (m--) {
            int a, b;
            scanf("%d %d", &a, &b);
            a++, b++; // 本题点号从0开始，+1后平移到1开始 0≤a,b<n
            add(a, b), add(b, a);
        }

        // 连通块的最大(多)数量
        ans = 0;

        int cnt = 0; // 原图中块数量(互相孤立的有多少个块)
        for (root = 1; root <= n; root++)
            if (!dfn[root]) {
                tarjan(root, -1);
                cnt++; // 记录有多少个独立的块
            }
        printf("%d\n", cnt + ans - 1);
    }
    return 0;
}