P3388 【模板】割點（割頂）

題目背景

割點

題目描述

給出一個n個點，m條邊的無向圖，求圖的割點。

輸入輸出格式

輸入格式：

第一行輸入n,m

下麵m行每行輸入x,y表示x到y有一條邊

輸出格式：

第一行輸出割點個數

第二行按照節點編號從小到大輸出節點，用空格隔開

輸入輸出樣例

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

1 
5

說明

n,m均為100000

tarjan 圖不一定聯通！！！

割點真是一個非常神奇的東西。

雖然和tarjan很像，

而且能理解其中的奧秘。

但是代碼還是看的一臉矇蔽，。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<queue>
 6 #include<algorithm>
 7 #include<stack> 
 8 #define lli long long int 
 9 using namespace std;
10 const int MAXN=1000001;
11 const int maxn=0x7fffff;
12 inline void read(int &n)
13 {
14     char c='+';int x=0;bool flag=0;
15     while(c<'0'||c>'9')
16     {c=getchar();if(c=='-')flag=1;}
17     while(c>='0'&&c<='9')
18     {x=(x<<1)+(x<<3)+c-48;c=getchar();}
19     flag==1?n=-x:n=x;
20 }
21 int n,m;
22 struct node
23 {
24     int u,v,nxt;
25 }edge[MAXN];
26 int head[MAXN];
27 int num=1;
28 void add_edge(int x,int y)
29 {
30     edge[num].u=x;
31     edge[num].v=y;
32     edge[num].nxt=head[x];
33     head[x]=num++;
34 }
35 int dfn[MAXN];//dfs的順序
36 int low[MAXN];// 每個點能追溯到的最近公共祖先
37 int vis[MAXN];
38 int ans[MAXN];// 是否是割點 
39 int ansnum; //割點的數量 
40 int tot=0;
41 int tarjan(int now,int fa)
42 {
43     dfn[now]=low[now]=++tot;    
44     int ch=0;
45     for(int i=head[now];i!=-1;i=edge[i].nxt)
46     {
47         if(low[edge[i].v]!=0)
48             low[edge[i].u]=min(low[edge[i].u],dfn[edge[i].v]);
49         else 
50         if(low[edge[i].v]==0)
51         {
52             ch++;//孩子的數量
53             int nxt=tarjan(edge[i].v,edge[i].u);
54             low[edge[i].u]=min(low[edge[i].u],low[edge[i].v]);
55             if((fa==-1&&ch>1)||(fa!=-1&&dfn[edge[i].u]==low[edge[i].v]))
56             {
57                 if(!ans[edge[i].u])
58                 {
59                     ans[edge[i].u]=1;
60                     ansnum++;
61                 }
62             }
63         }
64     }
65     return low[now];
66 }
67 int main()
68 {
69     read(n);read(m);
70     memset(head,-1,sizeof(head));
71     for(int i=1;i<=m;i++)
72     {
73         int x,y;
74         read(x);read(y);
75         add_edge(x,y);
76         add_edge(y,x);
77     }
78     for(int i=1;i<=n;i++)
79         if(low[i]==0)
80             tarjan(i,-1);    
81     printf("%d\n",ansnum);
82     for(int i=1;i<=n;i++)
83         if(ans[i]==1)
84             printf("%d ",i);
85     return 0;
86 }