引入
連通圖
? 在一個無向圖\(G\)中，若從頂點\(i\) 到頂點\(j\)有路徑相連，則稱 \(i\)和\(j\)是連通的，如果圖中任意兩點都是連通的，那么圖被稱作連通圖，如果\(G\)是有向圖，則稱為強連通圖（注意：需要雙向都有路徑），如果是單向連通，則稱\(G\)為單向連通圖，
割點（關節點）
? 在無向連通圖\(G=(V,E)\)中: 若對于\(x\in V\)， 從圖中刪去節點\(x\)以及所有與\(x\)關聯的邊之后， \(G\)分裂成兩個或兩個以上不相連的子圖， 則稱\(x\)為\(G\)的割點， 簡而言之， 割點是無向連通圖中的一個特殊的點， 刪去中這個點后， 此圖不再連通， 而所以滿足這個條件的點所構成的集合即為割點集合，
割邊（橋）
? 如果洗掉\(G\)的一條邊\(b\)，圖\(G\)分離成兩個非空子圖，則稱邊\(b\)為圖\(G\)的橋，如下圖中，頂點\(u\)和\(v\)都是割點，其他頂點都不是割點，邊\((u,v)\)是橋，其他邊都不是橋，
關節點識別
方案一：DFS (O(n^2))
依次去掉每一個點，判斷圖是否還連通，
方案二： Tarjan 演算法
DFS樹
首先需要了解一些關于深度優先搜索樹（DFS tree）的概念，
以下圖為例：
它的深度優先搜索樹如下：
其中黑色的邊為樹邊：如果結點\(u\)因演算法對邊\((u,v)\)的搜索而首次被發現，則\((u,v)\)是一條樹邊，
簡單點說就是，它是正常的一顆樹的邊，只看\(1,2,3,4\)結點，是一顆樹，【箭頭只是表示搜索順序】
其中紅色的邊為反向邊：方向邊\((u,v)\)是將結點\(u\)連接到其\(dfs\)樹中的一個祖先結點\(v\)的邊，環也被認為是反向邊，
演算法步驟
首先選定一個根節點，從該根節點開始遍歷整個圖（使用\(DFS\)），
對于根節點，判斷是不是割點很簡單，計算其子樹數量就行，如果有2棵即以上的子樹，就是割點，因為如果去掉這個點，這兩棵子樹就不能互相到達，
對于非根節點，判斷是不是割點就有些麻煩了，我們維護兩個陣列\(dfn[]\)和\(low[]\)，
\(dfn[u]\)：意思就是在\(dfs\)的程序中，當前的\(u\)結點是第幾個（首次）被訪問的，（之前一直不知道這個\(dfn\)是個什么縮寫，豆腐腦？）
\(low[u]\)：表示頂點\(u\)及其子樹中的點，通過反向邊，能夠回溯到的最早的點（\(dfn\)最小）的\(dfn\)值，
對于邊\((u, v)\)，如果\(low[v]>=dfn[u]\)，此時\(u\)就是割點，
演算法可視為線性時間復雜度，采用鄰接表存盤的話，應與\(DFS\)相同，為\(O(V+E)\)
例題1：https://www.luogu.org/problem/P3388
#include <iostream>
#include <set>
#include <stdio.h>
using namespace std;
int cnt, Time = 1;
int Low[20005], d[20005];
bool fuck[20005];
struct Node {
int data;
Node* next;
Node() {}
Node(int data) :data(data) {};
void push(int to) {
Node* s = new Node(to);
s->next = next;
next = s;
}
}head[20005];
void DFS(int u, int father) {
int cnt = 0;
Low[u] = d[u] = Time++;
Node* p = head[u].next;
while (p) {
int v = p->data;
if (d[v] == -1) {//如果v尚未訪問
DFS(v, u);
if (Low[v] < Low[u])Low[u] = Low[v];
if (father != 0 && Low[v] >= d[u]) fuck[u] = true;
if (father == 0)
cnt++;
}
//如果v已經訪問，但不是v的雙親，則v是一條反向邊
Low[u] = Low[u] < d[v] ? Low[u] : d[v];
p = p->next;
}
if (father == 0 && cnt >= 2)fuck[u] = true;
}
int main() {
int i, n, m;
cin >> n >> m;
for (i = 1; i <= n; i++) {
d[i] = -1;
head[i].next = NULL;
}
for (i = 0; i < m; i++) {
int c1, c2;
//cin >> c1 >> c2;
scanf("%d%d", &c1, &c2);
head[c1].push(c2);
head[c2].push(c1);
}
for (int i = 1; i <= n; i++) {
if (d[i] == -1) DFS(i, 0);
}
//DFS(1, 0);
int res = 0;
for (int i = 1; i <= n; i++) {
if (fuck[i])res++;
}
cout << res << endl;
for (int i = 1; i <= n; i++) {
if (fuck[i])cout << i << ' ';
}
cout << endl;
return 0;
}
例題2： https://www.luogu.org/problem/P2341
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/136673.html
標籤：其他
上一篇：20191030-帶回傳值的回溯演算法Leetcode解數獨
下一篇：資料結構篇——二叉樹