题目背景

割点

题目描述

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

点的编号均大于0小于等于n

 

#include 
     
      using namespace std;using ll=long long;const int MAXN=1e5+10;struct node{    int v;    int Next;}edge[MAXN<<1 ];int head[MAXN], cnt,low[MAXN],dfn[MAXN],Time;bool vis[MAXN];void add(int u,int v){    edge[++cnt].v=v;    edge[cnt].Next=head[u];    head[u]=cnt;}void tarjan(int u,int fa){    dfn[u]=low[u]=++Time;    int child=0;    for (int i = head[u]; i !=-1 ; i=edge[i].Next) {        int v=edge[i].v;        if(!dfn[v]) {  //没有被访问过。            tarjan(v,fa);            low[u]=min(low[u],low[v]);            if(low[v]>=dfn[u]&&u!=fa)//一个点能连接到最远的祖先节点仍大于或者等于他的父亲节点，那么他的父亲节点一定是割点                vis[u]=1;            if(u==fa) child++;        }        low[u]=min(low[u],dfn[v]);//求割点时只能是dfn[v],强连通分量可以是dfn[v]||low[v]    }    if(child>=2&&u==fa)        vis[u]=1;}int main(){    int n,m;    scanf("%d%d",&n,&m);    memset(head,-1, sizeof(head));    int u,v;    for (int i = 0; i