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

说明

n,m均为100000

tarjan 图不一定联通！！！

分析

tarjan求割点

code

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #include<cmath>

 #include<cstdlib>

 using namespace std;

 const int N = ;

 struct Edge{

     int to,nxt;

 }e[N<<];

 int head[N],dfn[N],low[N];

 bool iscut[N];

 int tn,tot;

 inline char nc() {

     static char buf[],*p1 = buf,*p2 = buf;

     return p1==p2&&(p2=(p1=buf)+fread(buf,,,stdin),p1==p2) ? EOF : *p1++;

 }

 inline int read() {

     int x = ,f = ;char ch = nc();

     for (; ch<''||ch>''; ch = nc())

         if (ch=='-') f = -;

     for (; ch>=''&&ch<=''; ch = nc())

         x = x*+ch-'';

     return x * f;

 }

 void add_edge(int u,int v) {

     e[++tot].to = v,e[tot].nxt = head[u],head[u] = tot;

 }

 void tarjan(int u,int fa) {

     low[u] = dfn[u] = ++tn;

     int cnt_son = ;

     for (int i=head[u]; i; i=e[i].nxt) {

         int v = e[i].to;

         if (!dfn[v]) {

             cnt_son++;

             tarjan(v,u);

             low[u] = min(low[u],low[v]);

             if (low[v] >= dfn[u])

                 iscut[u] = true;

         }

         else if (dfn[v] < dfn[u] && v != fa)

             low[u] = min(low[u],dfn[v]);

     }

     if (fa< && cnt_son==) iscut[u] = false;

 }

 int main() {

     int n = read(),m = read();

     for (int u,v,i=; i<=m; ++i) {

         u = read(),v = read();

         add_edge(u,v),add_edge(v,u);

     }

     for (int i=; i<=n; ++i)

         if (!dfn[i]) tarjan(i,-);

     int ans = ;

     for (int i=; i<=n; ++i)

         if (iscut[i]) ans++;

     printf("%d\n",ans);

     for (int i=; i<=n; ++i)

         if (iscut[i]) printf("%d ",i);

     return ;

 }