电力

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 2049 字
多组数据，每组给P个点C条无向边，求删掉一个
一本通
练习
正文

// 原题：https://oj.yecheng.tv/p/T1525
// 题意：多组数据，每组给 P 个点 C 条无向边（点号从 0 开始，保证无重边），求删掉一个点后最多能剩下多少个连通块，读入以 0 结束。
// 思路：先数出原图连通块数 tot，再跑 Tarjan 求割点：对 DFS 树的根删掉它多出「儿子个数」个块，对非根结点 u 删掉它多出 1 加上「满足 low[v] >= dfn[u] 的儿子个数」个块，取最大值。
// 1. 删点 u 的答案等于 tot - 1 加上 u 在它自己那个连通块里新切出来的块数，孤立点的贡献是 0。
// 2. 根结点没有祖先方向，所以它切出来的块数就是儿子个数，不需要再加 1。
// 复杂度：O(P + C) 时间 / O(P + C) 空间
// 易错点：点号从 0 开始，遍历与判连通都要覆盖 0 到 P - 1，漏掉 0 号点会多算一个连通块。
// 易错点：孤立点（度为 0）也要参与取最大值，它删掉后连通块数只会减少 1，不能跳过不枚举。
#include <bits/stdc++.h>
using namespace std;
const int MAXP = 10005;
vector<int> g[MAXP];
int dfn[MAXP], low[MAXP], idx;
int add[MAXP];
bool vis[MAXP];
void dfsComp(int u){
    vis[u] = true;
    for(int k = 0; k < (int)g[u].size(); k++){
        int v = g[u][k];
        if(!vis[v]) dfsComp(v);
    }
}
void tarjan(int u, int root){
    dfn[u] = low[u] = ++idx;
    int child = 0;
    for(int k = 0; k < (int)g[u].size(); k++){
        int v = g[u][k];
        if(!dfn[v]){
            child++;
            tarjan(v, root);
            low[u] = min(low[u], low[v]);
            if(u != root && low[v] >= dfn[u]) add[u]++;
        }else{
            low[u] = min(low[u], dfn[v]);
        }
    }
    if(u == root) add[u] = child;
}
int main(){
    int P, C;
    while(cin >> P >> C){
        if(P == 0) break;
        for(int i = 0; i <= P; i++){
            g[i].clear();
            dfn[i] = 0;
            low[i] = 0;
            add[i] = 0;
            vis[i] = false;
        }
        for(int i = 0; i < C; i++){
            int a, b;
            cin >> a >> b;
            g[a].push_back(b);
            g[b].push_back(a);
        }
        int tot = 0;
        for(int i = 0; i < P; i++){
            if(!vis[i]){
                tot++;
                dfsComp(i);
            }
        }
        idx = 0;
        for(int i = 0; i < P; i++){
            if(!dfn[i]) tarjan(i, i);
        }
        int ans = 0;
        for(int i = 0; i < P; i++){
            int cur = tot - 1 + add[i];
            if(cur > ans) ans = cur;
        }
        cout << ans << "\n";
    }
    return 0;
}
电力

正文

一本通·提高篇的其它内容
