感性理解：
o(*￣︶￣*)o ^_^ \(^o^)/~
1.
当根节点有大于两个儿子时，割掉它，剩下的点必然不联通（有两个强连通分量），则他为割点。
那么对于非根节点，在无向图G中，刚且仅当点u存在一个可遍历到的后代v，且点v无法走回点u的前辈时，点u就为割点。
洛谷P3388
1 #include<iostream>
2 #include<cstdio>
3 using namespace std;
4 const int N=1e5+2;
5 int n,m,idx,cnt,tot,h[N];
6 struct node{
7 int v,ne;
8 }e[N*3];
9 int ans[N];
10 void add(int u,int v)
11 {
12 tot++;e[tot]=(node){v,h[u]};h[u]=tot;
13 }
14 int dfn[N],low[N];
15 bool cut[N];
16 void tarjan(int u,int fa)
17 {
18 dfn[u]=low[u]=++idx;
19 int ch=0;
20 for(int i=h[u],rr;i;i=e[i].ne)
21 {
22 rr=e[i].v;
23 if(!dfn[rr])
24 {
25 tarjan(rr,u);
26 low[u]=min(low[u],low[rr]);
27 if(low[rr]>=dfn[u] && u!=fa) cut[u]=1;
28 ch++;
29 }
30 low[u]=min(low[u],dfn[rr]);
31 }
32 if(ch>=2&&u==fa) cut[u]=1;
33 }
34 int main()
35 {
36 scanf("%d%d",&n,&m);
37 for(int i=1,x,y;i<=m;++i)
38 {
39 scanf("%d%d",&x,&y);
40 add(x,y);add(y,x);
41 }
42 tot=0;
43 for(int i=1;i<=n;++i)
44 if(!dfn[i]) tarjan(i,i);
45 for(int i=1;i<=n;++i)
46 if(cut[i]) ans[++tot]=i;
47 printf("%d\n",tot);
48 for(int i=1;i<=tot;++i) printf("%d ",ans[i]);
49 return 0;
50 }
=================================================================================================
ZOJ2588
1 #include<bits/stdc++.h>
2 using namespace std;
3 const int N=1e5+2;
4 int n,m,idx,cnt,tot,h[N];
5 struct node{
6 int v,ne,id,fg; //会有重边，所以标记一下，
7 }e[N*3];//注意，图中可能有重边，只要顶点u和v之间有重边，则这些重边任何一条都不可能是割边。
8 int ans[N],fg;
9 void add(int u,int v,int id)
10 {
11 fg=1;
12 for(int i=h[u];i;i=e[i].ne)
13 if(e[i].v==v) e[i].fg=0,fg=0;
14 tot++;e[tot]=(node){v,h[u],id,fg};h[u]=tot;
15 }
16 int dfn[N],low[N];
17 void tarjan(int u,int fa)
18 {
19 dfn[u]=low[u]=++idx;
20 for(int i=h[u],rr;i;i=e[i].ne)
21 {
22 rr=e[i].v;
23 if(rr==fa) continue;
24 if(!dfn[rr])
25 {
26 tarjan(rr,u);
27 low[u]=min(low[u],low[rr]);
28 if(low[rr]>dfn[u] && e[i].fg) ans[++tot]=e[i].id;
29 }
30 low[u]=min(low[u],dfn[rr]);
31 }
32 }
33 int T;
34 int main()
35 {
36 scanf("%d",&T);
37 while(T--)
38 {
39 tot=0;idx=0;
40 scanf("%d%d",&n,&m);
41 for(int i=1;i<=n;++i) h[i]=0,dfn[i]=0,low[i]=0;
42 for(int i=1,x,y;i<=m;++i)
43 {
44 scanf("%d%d",&x,&y);
45 add(x,y,i);add(y,x,i);
46 }tot=0;
47 for(int i=1;i<=n;++i)
48 if(!dfn[i]) tarjan(i,i);
49 printf("%d\n",tot);
50 sort(ans+1,ans+tot+1);
51 if(tot)
52 {
53 printf("%d",ans[1]);
54 for(int i=2;i<=tot;++i) printf(" %d",ans[i]);
55 printf("\n");
56 }
57 if(T) printf("\n");
58 }
59 return 0;
60 }
61 /*
62 Sample Input
63 2
64
65 6 7
66 1 2
67 2 3
68 2 4
69 5 4
70 1 3
71 4 5
72 3 6
73
74 10 16
75 2 6
76 3 7
77 6 5
78 5 9
79 5 4
80 1 2
81 9 8
82 6 4
83 2 10
84 3 8
85 7 9
86 1 4
87 2 4
88 10 5
89 1 6
90 6 10
91
92 Sample Output
93 2
94 3 7
95
96 1
97 4
98
99 */
==================================================================================================
至于边-双连通分量是指在一个无向图中两点间至少有两条路径，且路径中的边不同。
边-双连通分量中一定没有桥。而桥是指当删去这个边时，连通块的数量会增加。
51nod 1076
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<cstring> 5 #include<string> 6 #include<cmath> 7 using namespace std; 8 const int N=3e5+10; 9 int n,m,tot,h[N]; 10 struct node{ 11 int v,ne; 12 }e[N*4]; 13 int dfn[N],low[N],idx; 14 void add(int u,int v) 15 { 16 tot++;e[tot]=(node){v,h[u]};h[u]=tot; 17 } 18 bool in[N]; 19 int Q,x,y,bg[N],s[N],top; 20 void dfs(int u,int fa) 21 { 22 dfn[u]=low[u]=++idx; 23 s[++top]=u;in[u]=1; 24 for(int i=h[u],rr;i;i=e[i].ne) 25 { 26 rr=e[i].v; 27 if(rr==fa) continue; 28 if(!dfn[rr]) 29 { 30 dfs(rr,u); 31 low[u]=min(low[u],low[rr]); 32 }else if(in[rr]) low[u]=min(low[u],low[rr]); 33 } 34 if(low[u]==dfn[u]) 35 { 36 do{ 37 in[s[top]]=0; 38 bg[s[top]]=u; 39 }while(s[top--]!=u); 40 } 41 } 42 int main() 43 { 44 scanf("%d%d",&n,&m); 45 for(int i=1;i<=m;++i) 46 { 47 scanf("%d%d",&x,&y); 48 add(x,y);add(y,x); 49 } 50 for(int i=1;i<=n;++i) 51 if(!dfn[i]) dfs(i,i); 52 scanf("%d",&Q); 53 while(Q--) 54 { 55 scanf("%d%d",&x,&y); 56 if(bg[x]==bg[y]) puts("Yes"); 57 else puts("No"); 58 } 59 return 0; 60 }
原文：https://www.cnblogs.com/adelalove/p/9830619.html