被坑了 n 个 WA

Problem

给一个无向图，删除某个点后问最大的连通块个数

Solution

处理出点双，割点共用的点双个数为 n 的话，会往原先连通块的个数 +n-1。

坑在于如果全部都是孤立点的话，连通块个数会 -1。

Code

// Code by ajcxsu
// Problem: electric

#include<bits/stdc++.h>
#define CLR(x) memset(x, 0, sizeof(x))
using namespace std;

const int N=1e6+10, M=4e6+10;
int h[N], to[M], nexp[M], p=1;
inline void ins(int a, int b) { nexp[p]=h[a], h[a]=p, to[p]=b, p++; }

vector<int> dcc[N];
int col[N], stk[N], dfn[N], low[N], t, idx, sidx, rt, cnt[N];
char cut[N];
void tarjan(int x) {
    dfn[x]=low[x]=++idx, stk[++t]=x;
    if(x==rt && !h[x]) { dcc[++sidx].push_back(x); return; }
    int cnt=0;
    for(int u=h[x];u;u=nexp[u])
        if(!dfn[to[u]]) {
            tarjan(to[u]), low[x]=min(low[x], low[to[u]]);
            if(low[to[u]]>=dfn[x]) {
                ++cnt;
                if(x!=rt || cnt>1) cut[x]=1;
                ++sidx;
                do {
                    dcc[sidx].push_back(stk[t]);
                } while(stk[t--]!=to[u]);
                dcc[sidx].push_back(x);
            }
        }
        else low[x]=min(low[x], dfn[to[u]]);
}

int main() {
    ios::sync_with_stdio(false);
    int n, m;
    while(cin>>n>>m, n) {
        CLR(h), p=1;
        int u, v;
        for(int i=0;i<m;i++) cin>>u>>v, ins(u, v), ins(v, u);
        sidx=idx=0, CLR(dfn), CLR(low), CLR(cut), CLR(cnt);
        for(int i=1;i<=n;i++) dcc[i].clear();
        int ini=0, ans=0;
        for(int i=0;i<n;i++)
            if(!dfn[i]) t=0, rt=i, tarjan(i), ini++;
        for(int i=1;i<=sidx;i++)
            for(int j=0, k=dcc[i].size(); j<k; j++) {
                v=dcc[i][j];
                if(cut[v]) cnt[v]++;
            }
        for(int i=0;i<n;i++)
            if(cut[i]) ans=max(ans, ini+cnt[i]-1);
        for(int i=1;i<=sidx;i++)
            ans=max(ans, ini-(dcc[i].size()==1));
        cout<<ans<<endl;
    }
    return 0;
}

本文链接：https://pst.iorinn.moe/archives/lsyoj-electricity.html
许可： https://pst.iorinn.moe/license.html
若无特别说明，博客内的文章默认将采用 CC BY 4.0 许可协议 进行许可☆