1-（tarjan-求联通块个数-分别列举去掉每个点的情况）

https://ac.nowcoder.com/acm/contest/7501/D
思路：用Tarjan算法的思路来写，dfn[i]代表结点 i 的dfs序，low[i]代表从结点 i dfs下去能到达的dfn值最小的结点的dfn值。
若x为当前结点，y为一个x的未被访问过的子节点，若对 y dfs完毕后，得到 low[y] >= dfn[x]则说明从x的父亲结点，经过x能够到达y，如果把结点x删掉，则不能到达结点y了。
这就相当于删去结点x时，x的父亲结点与结点y会被分成两个连通块，即这两部分无法相互到达，因此只需要数一下对于结点x，它有多少个儿子结点y，满足low[y]>=dfn[x]，当然其实x的父亲结点也算是一个儿子节点，因此需要+1表示算上父亲节点。但每次dfs的起点是没有父亲节点的，所以不需要+1.

综上所述，删去一个结点x会造成怎样的影响呢？假设删去结点x会增加ans[x]个连通块，这个无向图初始包含m个连通块，这个节点原来是属于1个连通块的，它删去后会增加ans[x]个连通块，那么删去这个结点后连通块的数量应为m-1+ans[x]。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=3e5+10;
int head[N],ver[N<<1],Next[N<<1];
int dfn[N],low[N],ans[N];
int n,m,tot,root,num=0,sum=0;
void add(int x,int y){
    ver[++tot]=y,Next[tot]=head[x],head[x]=tot;
}
void tarjan(int x){
    dfn[x]=low[x]=++num;
    ans[x]=(x!=root);
    for(int i=head[x];i;i=Next[i]){
        int y=ver[i];
        if(!dfn[y]){
            tarjan(y);
            low[x]=min(low[x],low[y]);
            ans[x]+=(low[y]>=dfn[x]);
        }
        else    low[x]=min(low[x],dfn[y]);
    }
}
int main(){
    scanf("%d%d",&n,&m);
    tot=0;
    for(int i=1;i<=m;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        if(x==y)    continue;
        add(x,y);
        add(y,x);
    }
    for(int i=1;i<=n;i++)
        if(!dfn[i])    root=i,tarjan(i),sum++;
    for(int i=1;i<=n;i++)
        printf("%d%c",sum+ans[i]-1,i==n?'\n':' ');
    return 0;    
}