【洛谷 3388】割点

水深无声 2021-10-26 21:46 319阅读 0赞

## 题目背景 ##

割点

## 题目描述 ##

给出一个nnn个点，mmm条边的无向图，求图的割点。

## 输入输出格式 ##

**输入格式：**

第一行输入n,mn,mn,m

下面mmm行每行输入x,yx,yx,y表示xxx到yyy有一条边

**输出格式：**

第一行输出割点个数

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

## 输入输出样例 ##

**输入样例\#1：** 复制

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

**输出样例\#1：** 复制

1 
    5

## 说明 ##

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

点的编号均大于000小于等于nnn。

**tarjan图不一定联通。**

题解：模板割点题哈哈哈哈爽~

#include<bits/stdc++.h>
    #include<iostream>
    #include<algorithm>
    #include<queue>
    #include<cmath>
    #include<cstring>
    #include<cstdlib>
    #include<cstdio>
    using namespace std;
    const int N=200004;
    int cnt,head[N],low[N],dfn[N],cut[N];
    struct node{
        int next;
        int m;
    }e[N];
    int n,m,idx;
    void add (int x,int y){
        cnt++;
        e[cnt].next=y;
        e[cnt].m=head[x];
        head[x]=cnt;
    }
    void tarjan(int u,int fa){
        dfn[u]=low[u]=++idx; 
        int num=0;
        for(int i=head[u];i;i=e[i].m){
            int v=e[i].next;
            if(!dfn[v]){
                tarjan(v,fa);
                low[u]=min(low[u],low[v]);
                if(low[v]>=dfn[u] && u!=fa)
                   cut[u]=1;
                if(u==fa) num++;
            }
            low[u]=min(low[u],dfn[v]);
        }
        if(num>=2 && u==fa) 
            cut[u]=1;
    }
    int main(){
        freopen("3388.in","r",stdin);
        freopen("3388.out","w",stdout);
        scanf("%d %d",&n,&m);
        int a,b,ans=0;
        for(int i=1;i<=m;i++){
            scanf("%d %d",&a,&b);
            add(a,b); add(b,a);
        }
        for(int i=1;i<=n;i++)
            if(dfn[i]==0) tarjan(i,i);
        for(int i=1;i<=n;i++) 
            if(cut[i]!=0) ans++;
        cout<<ans<<endl;
        for(int i=1;i<=n;i++)
            if(cut[i]!=0) printf("%d ",i);
        return 0;
    }

转载于:https://www.cnblogs.com/wuhu-JJJ/p/11152560.html