在LC里面的圖論題幔亥，一般還是非吵芊恚基礎(chǔ)的，BFS帕棉，或者Dijkstra 為主针肥。
造成其實(shí)有很多經(jīng)典的圖論算法運(yùn)用的不多。也確實(shí)因?yàn)檫@類算法的運(yùn)用是比較難的問題瞒窒。
直到我遇到了1192. Critical Connections in a Network， 看來也并不是完全沒有。這道題本質(zhì)是求一個(gè)無向圖的邊雙連通分量巴比，是個(gè)模板題政勃。解法就是tarjan算法。無論是求有向圖的強(qiáng)聯(lián)通分量，還是無向圖的邊雙連通或點(diǎn)雙連通都可以用他的算法搞晨仑。而且時(shí)間復(fù)雜度還非常好答捕。
所以開個(gè)專題持际，總結(jié)一下他的連通算法思想。
下面的分析，主要偏向?qū)崙?zhàn)與應(yīng)用。
有向圖的強(qiáng)連通分量
所謂連通分量涤久，就是在一個(gè)有向圖里的一組點(diǎn)集剧罩。這個(gè)點(diǎn)集里的任意2個(gè)點(diǎn)都可以互相通過點(diǎn)集的邊走到對(duì)方幕与。
那么強(qiáng)連通分量就是這個(gè)極大的點(diǎn)集来氧。也就是說我們無法通過再添加一個(gè)點(diǎn)，使得該點(diǎn)集依然是連通分量。那么當(dāng)前這個(gè)點(diǎn)集就是一個(gè)強(qiáng)連通分量。
如上圖蹲嚣，圖中圈出的3個(gè)就是3個(gè)強(qiáng)連通分量疲眷。其中中間那個(gè)3個(gè)點(diǎn)的強(qiáng)連通分量里的任意2個(gè)點(diǎn)，都是一個(gè)連通分量。
有了強(qiáng)連通分量，我們可以通過把每個(gè)強(qiáng)連通的分量給縮成一個(gè)點(diǎn)，那么整個(gè)圖就會(huì)變成一個(gè)有向無環(huán)圖。有向無環(huán)圖就會(huì)有拓?fù)湫颍梢岳眠@個(gè)性質(zhì)解一些題目。
下面是tarjan 求強(qiáng)連通分量的一個(gè)偽代碼。
dfn[u] 是深度優(yōu)先搜索遍歷u時(shí)結(jié)點(diǎn) 被搜索的次序
low[u] : 設(shè)以 u為根的子樹為 subtree(u)。 low[u] 定義為以下結(jié)點(diǎn)的 dfn 的最小值： subtree(u) 中的結(jié)點(diǎn)彭沼；從 subtree(u)通過一條不在搜索樹上的邊能到達(dá)的結(jié)點(diǎn)敦冬。
一個(gè)結(jié)點(diǎn)的子樹內(nèi)結(jié)點(diǎn)的 dfn 都大于該結(jié)點(diǎn)的 dfn溶褪。
從根開始的一條路徑上的 dfn 嚴(yán)格遞增于游，low 嚴(yán)格非降。
按照深度優(yōu)先搜索算法搜索的次序?qū)D中所有的結(jié)點(diǎn)進(jìn)行搜索担忧。在搜索過程中，對(duì)于結(jié)點(diǎn) u 和與其相鄰的結(jié)點(diǎn) v （v 不是 u 的父節(jié)點(diǎn)）考慮 3 種情況：
v 未被訪問：繼續(xù)對(duì)v進(jìn)行深度搜索奶镶。在回溯過程中，用 low[v]更新 low[u] 斋否。因?yàn)榇嬖趶?u 到 v 的直接路徑奇徒，所以 v 能夠回溯到的已經(jīng)在棧中的結(jié)點(diǎn)胖笛，u 也一定能夠回溯到。
v 被訪問過，已經(jīng)在棧中：即v 已經(jīng)被訪問過麦萤，根據(jù) low值的定義（能夠回溯到的最早的已經(jīng)在棧中的結(jié)點(diǎn)）胶台，則用dfn[v] 更新 low[u] 赡矢。
v 被訪問過，已不在在棧中：說明 v已搜索完畢耸棒，其所在連通分量已被處理，所以不用對(duì)其做操作。
TARJAN_SEARCH(int u)
vis[u]=true
low[u]=dfn[u]=++dfncnt
push u to the stack
for each (u,v) then do
if v hasn't been search then
TARJAN_SEARCH(v) // 搜索
low[u]=min(low[u],low[v]) // 回溯
else if v has been in the stack then
low[u]=min(low[u],dfn[v])
下面給出一個(gè)JAVA 求強(qiáng)連通分量，可縮點(diǎn)的模板
int[] dfn, low, id;
boolean[] inStack;
Deque<Integer> stack;
int timestamp = 0, sccCnt = 0;
Set<Integer>[] gra;
void tarjan(int u) {
dfn[u] = low[u] = ++timestamp;
stack.push(u);
inStack[u] = true;
for (int v : gra[u]) {
if (dfn[v] == 0) {
tarjan(v);
low[u] = Math.min(low[v], low[u]);
} else if (inStack[v]) low[u] = Math.min(low[u], dfn[v]);
}
if (dfn[u] == low[u]) {
int y;
++sccCnt;
do {
y = stack.pop();
inStack[y] = false;
id[y] = sccCnt;
} while (y != u);
}
}
// 縮點(diǎn)后的有向無環(huán)圖
Set<Integer>[] dag;
void buildDAG(int n) {
dag = new Set[sccCnt];
for (int i = 0; i < n; i++) {
for (int v : gra[i]) {
if (id[i] != id[v])
dag[id[i]].add(id[v]);
}
}
}
強(qiáng)連通分量編號(hào)順序的逆序一定是拓?fù)湫?/strong>
無向圖的雙連通分量
無向圖里有2種連通分量实檀。
第一種叫邊雙連通分量渐裂，也稱為極大無橋柒凉。另一種叫點(diǎn)雙連通分量也稱為極大無割點(diǎn)鲤遥。
橋是一條無向邊，刪去后宇植，本來連通的圖會(huì)變得不連通梗逮。所以在一個(gè)邊的雙連通分量里，不管刪去哪1條邊绣溜，整個(gè)圖還是連通的慷彤，并且這個(gè)點(diǎn)集是極大的。
割點(diǎn)就是一個(gè)點(diǎn)怖喻，刪去這個(gè)點(diǎn)和他所關(guān)聯(lián)的邊之后底哗，整個(gè)圖變得不連通了。這個(gè)點(diǎn)稱為割點(diǎn)锚沸。點(diǎn)的雙連通分量就是極大的不包含割點(diǎn)的連通塊跋选。
一個(gè)割點(diǎn)至少屬于2個(gè)點(diǎn)連通分量。如下圖哗蜈，點(diǎn)B既是左半部分的點(diǎn)雙野建，也是右半部分的點(diǎn)雙。
如何找到橋
從X開始去搜Y恬叹，如果Y能到達(dá)它的祖先節(jié)點(diǎn)候生，說明有環(huán)。如果Y無論如何都走不到比X的DFN還要小的點(diǎn)绽昼。那么這個(gè)邊就是橋唯鸭。
所以一個(gè)邊是橋等價(jià)于dfn[x] < low[y]
1192. Critical Connections in a Network
求橋模板
List<List<Integer>> res = new ArrayList<>();
List<Integer>[] graph;
public List<List<Integer>> criticalConnections(int n, List<List<Integer>> connections) {
int[] dfn = new int[n], low = new int[n];
// use adjacency list instead of matrix will save some memory, adjmatrix will cause MLE
graph = new ArrayList[n];
for (int i = 0; i < n; i++) {
graph[i] = new ArrayList<>();
}
// build graph
for (int i = 0; i < connections.size(); i++) {
int from = connections.get(i).get(0), to = connections.get(i).get(1);
graph[from].add(to);
graph[to].add(from);
}
tarjan(0, low, dfn, -1);
return res;
}
int time = 0; // time when discover each vertex
private void tarjan(int u, int[] low, int[] dfn, int pre) {
dfn[u] = low[u] = ++time; // discover u
for (int v : graph[u]) {
if (dfn[v] == 0) { // if not discovered
tarjan(v, low, dfn, u);
low[u] = Math.min(low[u], low[v]);
if (low[v] > dfn[u]) {
// u - v is critical, there is no path for v to reach back to u or previous vertices of u
res.add(Arrays.asList(u, v));
}
} else if (v != pre) { // if v discovered and is not parent of u, update low[u], cannot use low[v] because u is not subtree of v
low[u] = Math.min(low[u], dfn[v]);
}
}
}
如果要把所有邊雙連通分量給縮點(diǎn)，只需要在TARJAN 方法進(jìn)來的時(shí)候硅确，把元素壓入棧目溉。然后當(dāng)dfn[u] == low[u] 時(shí)從棧里彈出，構(gòu)造出所有點(diǎn)的ID菱农。
在外面對(duì)如果1條邊不在一個(gè)邊雙連通分量里缭付，就可以加一條邊。
下面是縮點(diǎn)后新圖模板
int[] low, dfn, id;
Set<Integer>[] gra;
int timestamp = 0, dccCnt = 0;
Deque<Integer> stack = new ArrayDeque<>();
Map<Integer, Integer> bridges;
void tarjan(int u, int pre) {
low[u] = dfn[u] = ++timestamp;
stack.push(u);
for (int v : gra[u]) {
if (dfn[v] == 0) {
tarjan(v, u);
low[u] = Math.min(low[u], low[v]);
if (dfn[u] < low[v]) {
bridges.put(u, v);
bridges.put(v, u);
}
} else if (v != pre) low[u] = Math.min(low[u], dfn[v]);
}
if (low[u] == dfn[u]) {
int y;
dccCnt++;
do {
y = stack.pop();
id[y] = dccCnt;
} while (y != u);
}
}
Set<Integer>[] newGra;
void buildNewGraph() {
newGra = new Set[dccCnt];
for (int i = 0; i < dccCnt; i++) newGra[i] = new HashSet<>();
for (int i = 0; i < gra.length; i++) {
for (int v : gra[i]) {
if (bridges.getOrDefault(i, -1) == v)
newGra[id[i]].add(id[v]);
}
}
}
如何找割點(diǎn)
如果DFS序先搜到X然后由X到Y(jié)循未。
- 如果X不是根節(jié)點(diǎn)陷猫，且
low(y) >= dfn(x)那么X是一個(gè)割點(diǎn)。 - X是根節(jié)點(diǎn)，至少有2個(gè)子節(jié)點(diǎn)滿足這樣的條件绣檬， X才是割點(diǎn)足陨。
Set<Integer>[] gra;
int[] low, dfn;
boolean[] cut;
int timestamp = 0, cutCnt = 0, root;
void tarjan(int u) {
dfn[u] = low[u] = ++timestamp;
int flag = 0; // 當(dāng)前有幾個(gè)孩子是割點(diǎn)
for (int v : gra[u]) {
if (dfn[v] == 0) {
tarjan(v);
low[u] = Math.min(low[u], low[v]);
if (dfn[u] <= low[v]) {
flag++;
if ((u != root || flag > 1) && !cut[u]) {
cut[u] = true;
cutCnt++;
}
}
} else low[u] = Math.min(low[u], dfn[v]);
}
}
那么如何找到所有點(diǎn)雙連通分量呢？
我們要知道所有割點(diǎn)屬于多個(gè)點(diǎn)雙連通分量娇未。也就是這個(gè)幾個(gè)極大點(diǎn)集里可能含有同一個(gè)割點(diǎn)墨缘。
比如上面的圖，左右2個(gè)點(diǎn)雙連通分量都含有點(diǎn)B零抬。如果要縮點(diǎn)拆圖的話镊讼。我們一般會(huì)把割點(diǎn)單獨(dú)抽取出來。然后和每個(gè)點(diǎn)雙連通分量縮的點(diǎn)建立一條無向邊平夜。對(duì)于這張圖縮點(diǎn)后如下：
下面給出蝶棋，一個(gè)求出所有點(diǎn)雙連通分量的模板. 圖不要求完全連通。
Set<Integer>[] gra;
int[] low, dfn;
boolean[] cut;
int timestamp = 0, cutCnt = 0, dccCnt = 0, root;
Deque<Integer> stack;
List<Integer>[] dcc; // 每一個(gè)點(diǎn)雙連通分量含有的點(diǎn)編號(hào)
// dccCnt 代表有多少個(gè)點(diǎn)雙連通分量
void tarjan(int u) {
dfn[u] = low[u] = ++timestamp;
int flag = 0; // 記錄有幾個(gè)孩子是割點(diǎn)
if (gra[u].isEmpty()) { // 單個(gè)點(diǎn)自成一個(gè)點(diǎn)連通分量
dcc[++dccCnt].add(u);
return;
}
for (int v : gra[u]) {
if (dfn[v] == 0) {
tarjan(v);
low[u] = Math.min(low[u], low[v]);
if (dfn[u] <= low[v]) {
flag++;
if (!cut[u] && (u != root || flag > 1)) {
cut[u] = true;
cutCnt++;
}
dccCnt++;
int y;
do {
y = stack.pop();
dcc[dccCnt].add(y);
} while (y != v);
// 這里到Y(jié)很關(guān)鍵褥芒，因?yàn)樵購?次就會(huì)把割點(diǎn)U給彈出
dcc[dccCnt].add(u); // u 為割點(diǎn)嚼松， 屬于多個(gè)點(diǎn)連通分量嫡良，所以不用出棧
}
} else low[u] = Math.min(low[u], dfn[v]);
}
}
總結(jié)
- tarjan算法的核心是dfn 和 low數(shù)組锰扶。一般都是沒遍歷過就DFS下去，回溯上來更新LOW數(shù)組寝受。遍歷過會(huì)有不同的判斷條件坷牛。在強(qiáng)連通里是看子節(jié)點(diǎn)是否在棧里。在邊雙連通是看這個(gè)點(diǎn)是否是parent很澄。 在點(diǎn)雙連通里就是else了京闰。
- 在判斷橋的時(shí)候，使用dfn[u] < low[v] 甩苛，因?yàn)檫呺p連通是parent的時(shí)候不會(huì)去更新u(見第一條）蹂楣。 而點(diǎn)雙連通需要dfn[u] <= low[v]
- 一般要縮點(diǎn)建新圖，都會(huì)需要用到棧來保存元素讯蒲。都是剛進(jìn)DFS壓棧痊土。前2個(gè)算法都是在遍歷后判斷l(xiāng)ow[u] == dfn[u] 來彈棧。代表這個(gè)點(diǎn)是整個(gè)連通分量的進(jìn)入點(diǎn)墨林。因?yàn)橹髮儆谶@個(gè)連通分量的點(diǎn)low[u] 勢(shì)必會(huì)被更新的更小赁酝。不然就不連通了。
- 點(diǎn)雙連通則是在發(fā)現(xiàn)割點(diǎn)后去做這件事旭等。出棧和上面2種算法出到當(dāng)前節(jié)點(diǎn)U不同酌呆，是到V。因?yàn)楦铧c(diǎn)U要被算進(jìn)多個(gè)點(diǎn)連通分兩種搔耕。
- 仔細(xì)比較這3種算法隙袁。
彩蛋
HNOI2012 礦場(chǎng)搭建就是一道割點(diǎn)運(yùn)用的題目。
這道題就是求出所有的點(diǎn)雙連通分量。隨后依次遍歷每個(gè)分量藤乙。如果里面只有1個(gè)點(diǎn)猜揪，就必須設(shè)置一個(gè)出口。如果整個(gè)分量無割點(diǎn)坛梁，那么就可以任選2個(gè)作為出口而姐。
如果一些分量被割點(diǎn)相連。那么勢(shì)必有葉子分量（只含一個(gè)割點(diǎn)的為葉子分量）
我們只需在葉子分量這里的任一一個(gè)非割點(diǎn)的點(diǎn)建立出口即可划咐。
AC代碼 + 模板運(yùn)用
import java.util.*;
class Main {
Set<Integer>[] gra;
int[] low, dfn;
boolean[] cut;
int timestamp = 0, cutCnt = 0, dccCnt = 0, root;
Deque<Integer> stack = new ArrayDeque<>();
List<Integer>[] dcc;
void tarjan(int u) {
dfn[u] = low[u] = ++timestamp;
stack.push(u);
int flag = 0;
if (gra[u].isEmpty()) { // 單個(gè)點(diǎn)自成一個(gè)點(diǎn)連通分量
dccCnt++;
dcc[dccCnt].add(u);
return;
}
for (int v : gra[u]) {
if (dfn[v] == 0) {
tarjan(v);
low[u] = Math.min(low[u], low[v]);
if (dfn[u] <= low[v]) {
flag++;
if (!cut[u] && (u != root || flag > 1)) {
cut[u] = true;
cutCnt++;
}
dccCnt++;
int y;
do {
y = stack.pop();
dcc[dccCnt].add(y);
} while (y != v);
dcc[dccCnt].add(u); // u 為割點(diǎn)拴念， 屬于多個(gè)點(diǎn)連通分量，所以不用出棧
}
} else low[u] = Math.min(low[u], dfn[v]);
}
}
void solve() {
Scanner sc = new Scanner(System.in);
int idx = 0;
while (true) {
idx++;
int m = sc.nextInt();
timestamp = 0; cutCnt = 0; dccCnt = 0;
if (m == 0) break;
List<int[]> edges = new ArrayList<>();
int n = 0;
for (int i = m - 1; i >= 0; i--) {
int a = sc.nextInt(), b = sc.nextInt();
edges.add(new int[]{a,b});
n = Math.max(n, Math.max(a, b));
}
gra = new Set[n + 1]; dcc = new List[n + 1];
for (int i = 1; i <= n; i++) {
gra[i] = new HashSet<>();
dcc[i] = new ArrayList<>();
}
for (int[] e : edges) {
gra[e[0]].add(e[1]);
gra[e[1]].add(e[0]);
}
low = new int[n + 1]; dfn = new int[n + 1]; cut = new boolean[n + 1];
for (root = 1; root <= n; root++) {
if (dfn[root] == 0)
tarjan(root);
}
long cnt = 0, ans = 1;
for (int i = 1; i <= dccCnt; i++) {
if (dcc[i].size() == 1) {
cnt++;
} else {
int cutNum = 0, size = dcc[i].size();
for (int j : dcc[i]) if (cut[j]) cutNum++;
if (cutNum == 0) {
ans *= size * (size - 1) / 2;
cnt += 2;
} else if (cutNum == 1) {
cnt += 1;
ans *= size - 1;
}
}
}
System.out.println("Case " + idx + ": " + cnt + " " + ans);
}
}
public static void main(String[] args) {
new Main().solve();
}
}
