【割点】洛谷P3388

题目背景

割点

题目描述

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

输入输出格式

输入格式：

第一行输入n,m

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

输出格式：

第一行输出割点个数

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

输入输出样例

输入样例#1：

6 7
1 2
1 3
1 4
2 5
3 5
4 5
5 6

输出样例#1：

1 
5

说明

对于全部数据， 20000n≤20000， 100000m≤100000

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

tarjan图不一定联通。

/*****************************************************************************/

tarjan！tarjan！tarjan！重要的事情说三遍！

割点是跟着缩点一起学的QAQ

缩点在这里

割点板子：

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=100010;
bool vis[maxn];
int n,m,ans=0,cnt=0,num=0;
int dfn[maxn],low[maxn],head[maxn];
struct Edge{
    int next,to;
}cute[maxn<<1]; 

void build(int x,int y)
{
    cute[++cnt].next=head[x];
    cute[cnt].to=y;
    head[x]=cnt;
}

void tarjan(int x,int fa)
{
    dfn[x]=low[x]=++num;
    int child=0;
    for(int i=head[x];i;i=cute[i].next)
    {
        int y=cute[i].to;
        if(!dfn[y])
        {
            tarjan(y,fa);
            low[x]=min(low[x],low[y]);
            if(dfn[x]<=low[y]&&x!=fa) vis[x]=true;
            if(x==fa) child++;
        }
        low[x]=min(dfn[y],low[x]);
    }
    if(x==fa&&child>=2) vis[x]=true;
}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        build(x,y);build(y,x);
    }
    for(int i=1;i<=n;i++)
        if(!dfn[i]) tarjan(i,i);
    for(int i=1;i<=n;i++)
        if(vis[i]) ans++;
    printf("%d
",ans);
    for(int i=1;i<=n;i++)
        if(vis[i]) printf("%d ",i);
    return 0; 
}