# 洛谷P3388 【模板】割点（割顶）(tarjan求割点)

2018-02-28 07:46:28来源:cnblogs.com作者:自为风月马前卒人点击

## 输入输出样例

`6 71 21 31 42 53 54 55 6`

`1 5`

## 说明

n,m均为100000

tarjan 图不一定联通！！！

tarjan求割点，

`// luogu-judger-enable-o2#include<cstdio>#include<cstring>#include<algorithm>#define getchar() (S == T && (T = (S = BB) + fread(BB, 1, 1 << 15, stdin), S == T) ? EOF : *S++)char BB[1 << 15], *S = BB, *T = BB;using namespace std;const int MAXN=1e6+10;inline int read(){    char c=getchar();int x=0,f=1;    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}    return x*f;}struct node{    int u,v,nxt;}edge[MAXN];int head[MAXN],num=1;inline void AddEdge(int x,int y){    edge[num].u=x;    edge[num].v=y;    edge[num].nxt=head[x];    head[x]=num++;}int dfn[MAXN],low[MAXN],cut[MAXN],tot=0;int tarjan(int now,int fa){    int ch=0;    dfn[now]=low[now]=++tot;    for(int i=head[now];i!=-1;i=edge[i].nxt)    {        if(!dfn[edge[i].v])        {            tarjan(edge[i].v,fa);            low[now]=min(low[now],low[edge[i].v]);            if(low[edge[i].v]>=dfn[now]&&now!=fa) cut[now]=1;            if(now==fa) ch++;         }        low[now]=min(low[now],dfn[edge[i].v]);    }    if(now==fa&&ch>=2) cut[now]=1;}int main(){    #ifdef WIN32    freopen("a.in","r",stdin);    #else    #endif    memset(head,-1,sizeof(head));    int N=read(),M=read();    for(int i=1;i<=M;i++)    {        int x=read(),y=read();        AddEdge(x,y);        AddEdge(y,x);    }    for(int i=1;i<=N;i++)        if(!dfn[i])            tarjan(i,i);    int ans=0;    for(int i=1;i<=N;i++)        if(cut[i]) ans++;    printf("%d/n",ans);    for(int i=1;i<=N;i++)        if(cut[i]) printf("%d ",i);    return 0;}`