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

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

分享
第七城市

题目背景

割点

题目描述

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

输入输出格式

输入格式:

第一行输入n,m

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

输出格式:

第一行输出割点个数

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

输入输出样例

输入样例#1: 复制
6 71 21 31 42 53 54 55 6
输出样例#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;}
第七城市

最新文章

123

最新摄影

闪念基因

微信扫一扫

第七城市微信公众平台