首页 > 代码库 > 洛谷 P3388 【模板】割点

洛谷 P3388 【模板】割点

题目背景

割点

题目描述

给出一个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 图不一定联通!!!

 

屠龙宝刀点击就送

#include <algorithm>#include <ctype.h>#include <cstring>#include <cstdio>#define N 100005using namespace std;void read(int &x){    x=0;char ch=getchar();    while(!isdigit(ch)) ch=getchar();    while(isdigit(ch))    {        x=x*10+ch-0;        ch=getchar();    }}bool vis[N],cutpoint[N],cutedge[N];int ans[N],l,low[N],dfn[N],tim,n,m,cnt=-1,head[N];struct node{    int next,to;}edge[N<<1];void add(int u,int v){    ++cnt;    edge[cnt].next=head[u];    edge[cnt].to=v;    head[u]=cnt;}int min(int a,int b){return a>b?b:a;} void tarjan(int x,int pre){    low[x]=dfn[x]=++tim;    vis[x]=1;    int sum=0;    bool flag=false;    for(int i=head[x];i!=-1;i=edge[i].next)    {        if((i^1)!=pre)         if(!vis[edge[i].to])         {             sum++;            tarjan(edge[i].to,i);            if(low[edge[i].to]>=dfn[x]) flag=true;             low[x]=min(low[x],low[edge[i].to]);         }         else low[x]=min(low[x],dfn[edge[i].to]);    }    if(pre==-1)    {        if(sum>1) cutpoint[x]=true;    }     else    {        if(flag) cutpoint[x]=true;    } }int main(){    memset(head,-1,sizeof(head));    read(n);read(m);    for(int x,y;m--;)    {        read(x);read(y);        add(x,y);        add(y,x);    }    for(int i=1;i<=n;i++)        if(!vis[i]) tarjan(i,-1);    for(int i=1;i<=n;i++)        if(cutpoint[i]) l++,ans[l]=i;    printf("%d\n",l);    for(int i=1;i<=l;i++) printf("%d ",ans[i]);    return 0;}

 

洛谷 P3388 【模板】割点