一，概念
1. 割點：如果去掉一個點以及與它連接的邊，該點原來所在的圖被分成兩部分（不連通），則稱該點為割點。
2. 割邊：如果去掉一條邊，該邊原來所在的圖被分成兩部分（不連通），則稱該點為割邊。
上圖中的點A ,B為割點，C則不是。 AB為割邊，BC則不是。
二，tarjan算法的應用
1. 變量說明：
① vector<int> edge[1000]; 存儲邊的信息
② bool cut[1000], bridge[1000][1000];
cut[x] == true 代表x為割點
bridge[x][y] == true代表邊xy為割邊
③ low[1000], dfn[1000], vis[1000]
vis代表訪問情況，0代表未訪問，1代表正在訪問，2代表已訪問
2. 重要的兩個數組 low 和 dfn：
① dfn：代表該節點被訪問的次序。對於數組 dfn ，使用一個全局變量tim進行賦值，每訪問到一個新節點 X ( 即vis[X]==0 ),則 dfn[X]=tim++;
② low[X]：代表 X節點與X節點的子樹 能回溯到的 最小的dfn值。
什麼是回邊？什麼時候需要進行low值的回溯更新？舉個栗子。
初始化三個數組的值均為零
一開始按1->2->3->4訪問，未遇到回邊
在訪問一個新節點X時，令low[X]=dfn[X]=tim++
此時節點4有兩條邊，4-2和4-5，由於節點2處於正在訪問的狀態，因此由4往2進行的邊就叫回邊，遇到回邊則要更新low[4]的值，low[4]=min(low[4],dfn[2])
可以發現，對於每一條回邊，都是指向瞭dfn值更小的點。
圖中綠色邊為回邊，low[4]的值更新
遞歸到6-1的情況
此時進行瞭回邊的更新有4-2 以及 6-1
接下來就是在每個遞歸程序結尾的回溯更新父親節點low值，即
low[父親節點] = min ( low[父親節點]，low[子節點] )
最終結果
三，判斷割點和割邊
1, 割點：
①該點為根節點時，若子樹數量大於一則說明該點為割點（子樹數量不等於與該點連接的邊數）。
②該點不為根節點時，若存在一個兒子節點的low值大於或等於該點的dfn值時（low[子節點] >= dfn[父節點]），該點為割點（即子節點，無法通過回邊，到達某一部分節點（這些節點的dfn值小於父親節點））。
2, 割邊：對於任意有邊連接的點u，v ，若low[u] > dfn[v]，則說明邊u-v為一條割邊。
四，代碼和註釋
接口：void cut_bri(int cur,int pop) ////cur為當前節點 pop為父親節點
復雜度： O( |V|+|E| )
設根節點的父親節點為-1
#include <iostream>
#include <string.h>
#include <string>
#include <algorithm>
#include <math.h>
#include <vector>
using namespace std;
const int maxn = 123456;
int n, m, dfn[maxn], low[maxn], vis[maxn], ans, tim;
bool cut[maxn];
vector<int> edge[maxn];
void cut_bri(int cur, int pop)
{
vis[cur] = 1;
dfn[cur] = low[cur] = ++tim;
int children = 0; ////子樹
for (int i : edge[cur]) ////對於每一條邊
{
if (i == pop || vis[cur] == 2)
continue;
if (vis[i] == 1) ////遇到回邊
low[cur] = min(low[cur], dfn[i]); ////回邊處的更新 (有環)
if (vis[i] == 0)
{
cut_play(i, cur);
children++; ////記錄子樹數目
low[cur] = min(low[cur], low[i]); ////父子節點處的回溯更新
if ((pop == -1 && children > 1) || (pop != -1 && low[i] >= dfn[cur])) ////判斷割點
{
if (!cut[cur])
ans++; ////記錄割點個數
cut[cur] = true; ///處理割點
}
if(low[i]>dfn[cur]) ////判斷割邊
{
bridge[cur][i]=bridge[i][cur]=true; ////low[i]>dfn[cur]即說明(i,cur)是橋(割邊)；
}
}
}
vis[cur] = 2; ////標記已訪問
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i++)
{
int x, y;
scanf("%d%d", &x, &y);
edge[x].push_back(y);
edge[y].push_back(x);
}
for (int i = 1; i <= n; i++)
{
if (vis[i] == 0)
cut_bri(i, -1); ////防止原來的圖並不是一個連通塊
////對於每個連通塊調用一次cut_bri
}
printf("%dn", ans);
for (int i = 1; i <= n; i++) ////輸出割點
if (cut[i])
printf("%d ", i);
return 0;
}