AcWing 1183 电力

题目传送门

一、核心思路

• 图可能不是完全连通的，需要遍历每个连通块
• 每个连通块内找下是否存在割点
• (1)如果存在，尝试下删除它后会产生多少个新的连通块\(s\)，就能增加\(s-1\)个连通块
• (2)如果不存在,那么没有可以删除的,换句话说，删除哪个节点，最终还是原来那些连通块
• 在通过割点求连通块时，需要特判根节点，不是根节点，还需要加上通往根节点那条边指向的连通块
  

二、实现代码

#include 
using namespace std;

const int N = 10010, M = 30010;
int n, m;
//邻接表
int e[M], h[N], idx, ne[M];
void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
int dfn[N], low[N], timestamp;
int root, ans;
//无向图点双连通性  v?DCC
//非割点标准模板，而是利用割点的代码，扩展出了“如果删除某个割点后，会产生出多少个连通块”
void tarjan(int u) {
    dfn[u] = low[u] = ++timestamp;
    int s = 0;
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        if (!dfn[j]) {
            tarjan(j);
            low[u] = min(low[u], low[j]);
            // j到不了u和u的祖先结点，所以u是割点，删去u会增加连通块个数
            if (low[j] >= dfn[u]) s++;
        } else
            low[u] = min(low[u], dfn[j]);
    }
    if (u != root) s++; // u不是根节点的话，出了自己的子树，还有他的父节点也成为了独立连通块
    ans = max(ans, s);
}
int main() {
    while (cin >> n >> m, n || m) {
        //多组测试数据，清空
        memset(dfn, 0, sizeof dfn); // dfn此题用来判断是已经在某个连通块中了，需要清零
        // memset(low, 0, sizeof low); low在使用过程中会被重新赋值，不需要清零
        memset(h, -1, sizeof h);
        idx = timestamp = 0;
        for (int i = 0; i < m; i++) {
            int a, b;
            cin >> a >> b;
            add(a, b), add(b, a);
        }
        ans = 0; //把每个连通块中的割点删除掉的话，可以产生的连通块个数最多是多少,即1->ans
        //如果所有连通块都不存在割点，那么ans=1

        int cnt = 0; //连通块数量
        //枚举每个节点，以tarjan计算每个连通块的内部割点情况
        for (root = 0; root < n; root++)
            if (!dfn[root]) { //如果点root没搜索过，说明在整体上是一个独立的连通块
                cnt++;        //连通块数+1
                tarjan(root); //类似于割点算法，计算以root为根的子树中删除任意割点后连通块个数
            }
        cout << ans + cnt - 1 << endl;
    }
    return 0;
}