首页 > > 程序设计 > C/C++ >

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

2018-06-17 21:09:18来源：未知阅读 ()

题目背景

割点

题目描述

给出一个n个点，m条边的无向图，求图的割点。

输入输出格式

输入格式：

第一行输入n,m

下面m行每行输入x,y表示x到y有一条边

输出格式：

第一行输出割点个数

第二行按照节点编号从小到大输出节点，用空格隔开

输入输出样例

输入样例#1：复制

输出样例#1：复制

1 
5

说明

n,m均为100000

tarjan 图不一定联通！！！

tarjan求割点，

若$low[v]>=dfn[u]$，说明从$v$不能走回$u$之前的点

那么$u$一定能将$v$与之前的点分割开

根节点需要特判，只有多于两个孩子时才是割点

// 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;
}