传送门:Router Mesh

题意

给你一个无向图,你需要求出每次删除$i$点(i=1,2,...,n)后,有多少个连通分量。

思路

  • 每次$dfs$能搜出一个连通分量,并求出每个点$u$在深度优先搜索生成树中往下有$child[u]$个子树分支。在$dfs$过程中,只有当!dfn[u]&&low[v]>=dfn[u]才有child[u]++(详见代码),因为这样$child[u]$统计的才是$u$点子树的数量。
  • 如果删除的点$u$是根节点,显然它是割点,删掉之后新增连通分量数为$child[u]$。
  • 否则,删掉之后新增连通分量数为$child[u]+1$,因为它的上方还有一个连通分量。

AC代码

#include <bits/stdc++.h>
using namespace std;
const int N=3e5+10;
int n,m;
vector<int>g[N];
bool fa[N];
int dfn[N],low[N];
int tim=0;
int child[N]; // 每个点的子树个数
void dfs(int u)
{
    dfn[u]=low[u]=++tim;
    int sz=g[u].size();
    for(int i=0;i<sz;i++)
    {
        int v=g[u][i];
        if(!dfn[v])
        {
            dfs(v);
            low[u]=min(low[u],low[v]);
            if(low[v]>=dfn[u])
                child[u]++;
        }
        else // 回退边
        {
            low[u]=min(low[u],dfn[v]);
        }
    }
}
void solve()
{
    int cnt=0;
    for(int i=1;i<=n;i++)
    {
        if(!dfn[i])
        {
            cnt++; // 初始时所有连通块个数
            fa[i]=1; // i是这个连通块的祖先节点
            dfs(i);
        }
    }
    for(int i=1;i<=n;i++)
    {
        if(fa[i])
        {
            child[i]=cnt-1+child[i];
        }
        else
        {
            child[i]=cnt-1+child[i]+1;
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>m;
    int x,y;
    for(int i=1;i<=m;i++)
    {
        cin>>x>>y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    solve();
    for(int i=1;i<=n;i++)
        i==n?printf("%d\n",child[i]):printf("%d ",child[i]);
    return 0;
}
/*
5 1
1 2
ans:4 4 3 3 3

6 5
1 2
2 3
3 1
4 5
5 6
ans:2 2 2 2 3 2
*/

还有就是被牛客的编译环境搞了一波心态:如果把dfs函数返回值写成int,然后又没return,洛谷的在线IDE和本地codeblocks没一点问题,提交到牛客就会给你错误(段错误或者超时)。