定義
無(wú)向圖有兩種雙連通分量
- 邊雙連通分量，e-DCC
- 點(diǎn)雙連通分量，v-DCC
橋：刪除這條無(wú)向邊后，圖變得不連通，這條邊被稱為橋
邊雙連通分量：極大的不含有橋的連通區(qū)域，說(shuō)明無(wú)論刪除e-DCC中的哪條邊，e-DCC依舊連通 （該連通分量的任意邊屬于原圖中的某條環(huán)）。此外，任意兩點(diǎn)之間一定包含兩條不相交（無(wú)公共邊）的路徑
割點(diǎn)：刪除該點(diǎn)（與該點(diǎn)相關(guān)的邊）后，圖變得不連通，這個(gè)點(diǎn)被稱為割點(diǎn)
點(diǎn)雙連通分量：極大的不含有割點(diǎn)的連通區(qū)域
一些性質(zhì)：
- 每個(gè)割點(diǎn)至少屬于兩個(gè)連通分量
- 任何兩個(gè)割點(diǎn)之間的邊不一定是橋，任何橋兩邊的端點(diǎn)不一定是割點(diǎn)，兩者沒(méi)有必然聯(lián)系，一個(gè)點(diǎn)連通分量也不一定是邊連通分量
Tarjan求e-DCC
無(wú)向圖不存在橫叉邊
和有向圖的強(qiáng)連通分量類似，引入dfn和low兩個(gè)數(shù)組
如何找到橋？判斷x->y的y是否能走到x之前（祖先節(jié)點(diǎn)），如果能走到，x和y在一個(gè)環(huán)中，刪除這條邊，其他點(diǎn)依然是連通的
所以x->y為橋：dfn[x] < low[y]
如何找到所有邊的雙連通分量？
- 刪除所有橋
- 或者用stk輔助，若
dfn[x] == low[x]，說(shuō)明x出發(fā)一定走不到x的祖先節(jié)點(diǎn)，那么x和其父節(jié)點(diǎn)之間的邊是橋，此時(shí)還在stk中的點(diǎn)為e-DCC的節(jié)點(diǎn)
這里使用第二種方式，模板：
void tarjan(int x, int from)
{
dfn[x] = low[x] = ++ tp;
stk[ ++ tt] = x;
for (int i = h[x]; i != -1; i = ne[i])
{
int y = e[i];
if (!dfn[y])
{
tarjan(y, i);
low[x] = min(low[x], low[y]);
}
else if (i != (from ^ 1))
low[x] = min(low[x], dfn[y]);
if (dfn[x] < low[y])
st[i] = st[i ^ 1] = true;
}
if (dfn[x] == low[x])
{
int y;
cnt ++ ;
do {
y = stk[tt -- ];
id[y] = cnt;
} while (x != y);
}
}
由于無(wú)向圖要存儲(chǔ)兩條有向邊，并且從數(shù)組的0下標(biāo)開(kāi)始存儲(chǔ)，所以0，1、2，3…這樣一對(duì)的邊是互相反向的邊，即i和i ^ 1為反向邊
為什么與有向圖的強(qiáng)連通分量不同，邊雙連通分量不需要使用st數(shù)組以標(biāo)記棧中的元素？
因?yàn)闊o(wú)向圖不存在橫叉邊的概念，就不會(huì)出現(xiàn)：x->y而y的dfn小于x，因?yàn)樵跓o(wú)向圖中y一定會(huì)向x遍歷
Tarjan求v-DCC
如何求割點(diǎn)？low[y] >= dfn[x]，刪除x節(jié)點(diǎn)后，y就是一顆獨(dú)立的子樹(shù)
- 如果x不是根節(jié)點(diǎn)，那么x是一個(gè)割點(diǎn)
- 如果x是根節(jié)點(diǎn)，至少有兩個(gè)y滿足以上關(guān)系
求割點(diǎn)的板子：
void tarjan(int x)
{
dfn[x] = low[x] = ++ tp;
int t = 0;
for (int i = h[x]; i != -1; i = ne[i])
{
int y = e[i];
if (!dfn[y])
{
tarjan(y);
low[x] = min(low[x], low[y]);
if (low[y] >= dfn[x]) t ++ ;
}
else low[x] = min(low[x], dfn[y]);
}
if (x != root) t ++ ;
ans = max(ans, t);
}
將每個(gè)v-DCC向其包含的割點(diǎn)連一條邊
縮點(diǎn)后，邊的數(shù)量不會(huì)增加，點(diǎn)的數(shù)量可能會(huì)增加到兩倍
tarjan求v-DCC與割點(diǎn)的板子：
一個(gè)孤立的點(diǎn)也是一個(gè)v-DCC，這里需要特判
若滿足條件：low[y] >= dfn[x]，那么y的子樹(shù)與x一起就是一個(gè)v-DCC
對(duì)于該節(jié)點(diǎn)是否是割點(diǎn)還需要特判，若該節(jié)點(diǎn)為根，并且與該節(jié)點(diǎn)相連的連通塊數(shù)量為1，那么該節(jié)點(diǎn)就不是一個(gè)割點(diǎn)
void tarjan(int x)
{
dfn[x] = low[x] = ++ tp;
stk[ ++ tt ] = x;
if (x == root && h[x] == -1)
{
++ dcnt;
dcc[dcnt].push_back(x);
return;
}
int t = 0; // 與x相連的連通塊數(shù)量
for (int i = h[x]; i != -1; i = ne[i])
{
int y = e[i];
if (!dfn[y])
{
tarjan(y);
low[x] = min(low[x], low[y]);
if (low[y] >= dfn[x])
{
dcnt ++, t ++ ;
if (x != root || t > 1) st[x] = true; // x為割點(diǎn)
int u;
do {
u = stk[tt -- ];
dcc[dcnt].push_back(u);
} while (u != y);
dcc[dcnt].push_back(x);
}
}
else low[x] = min(low[x], dfn[y]);
}
}
395. 冗余路徑
395. 冗余路徑 - AcWing題庫(kù)
任意兩點(diǎn)間都存在兩條沒(méi)有重復(fù)邊的路徑，等價(jià)于整個(gè)圖是一個(gè)雙連通分量
將無(wú)向連通圖的邊雙連通分量縮點(diǎn)后，得到的結(jié)構(gòu)是一顆樹(shù)，因?yàn)檫呺p連通分量是不包含橋的結(jié)構(gòu)，縮點(diǎn)后，圖中只含有橋，即刪除任意一條邊后，圖成為兩個(gè)連通塊，這是一個(gè)樹(shù)結(jié)構(gòu)
為了滿足題意，需要向這顆樹(shù)中添加邊，使之成為邊連通分量，那么要加幾條邊？
連接所有葉子節(jié)點(diǎn)，使這顆樹(shù)結(jié)構(gòu)成為雙連通分量，至少需要加 [ ( c n t + 1 ) / 2 ] [(cnt + 1) / 2] [(cnt+1)/2]然后再下取整的邊數(shù)，也就是將每個(gè)葉子節(jié)點(diǎn)相連，使環(huán)滿足雙連通分量的性質(zhì)
注意cnt為1時(shí)需要特判
#include <iostream>
#include <cstring>
using namespace std;
const int N = 5010, M = 10010;
int h[N], e[M], ne[M], idx;
int dfn[N], low[N], tp, cnt;
int stk[N], tt, id[N];
bool st[N]; int d[N];
int n, m;
void add(int x, int y)
{
e[idx] = y, ne[idx] = h[x], h[x] = idx ++ ;
}
void tarjan(int x, int from)
{
dfn[x] = low[x] = ++ tp;
stk[ ++ tt] = x;
for (int i = h[x]; i != -1; i = ne[i])
{
int y = e[i];
if (!dfn[y])
{
tarjan(y, i);
low[x] = min(low[x], low[y]);
if (dfn[x] < low[y])
st[i] = st[i ^ 1] = true;
}
else if (i != (from ^ 1))
low[x] = min(low[x], dfn[y]);
}
if (dfn[x] == low[x])
{
int y;
cnt ++ ;
do {
y = stk[tt -- ];
id[y] = cnt;
} while (x != y);
}
}
int main()
{
memset(h, -1, sizeof(h));
scanf("%d%d", &n, &m);
int x, y;
for (int i = 0; i < m; ++ i )
{
scanf("%d%d", &x, &y);
add(x, y), add(y, x);
}
tarjan(1, -1);
for (int i = 0; i < idx; i ++ )
if (st[i])
d[id[e[i]]] ++ ;
int res = 0;
for (int i = 1; i <= cnt; ++ i )
if (d[i] == 1) res ++ ;
if (cnt == 1) puts("0");
else printf("%d\n", (res + 1) / 2);
return 0;
}
debug：^的優(yōu)先級(jí)小于!=
可以不使用st數(shù)組標(biāo)記橋：
#include <iostream>
#include <cstring>
using namespace std;
const int N = 5010, M = 10010;
int h[N], e[M], ne[M], idx;
int dfn[N], low[N], tp, cnt;
int stk[N], tt, id[N];
int d[N];
int n, m;
void add(int x, int y)
{
e[idx] = y, ne[idx] = h[x], h[x] = idx ++ ;
}
void tarjan(int x, int from)
{
dfn[x] = low[x] = ++ tp;
stk[ ++ tt] = x;
for (int i = h[x]; i != -1; i = ne[i])
{
int y = e[i];
if (!dfn[y])
{
tarjan(y, i);
low[x] = min(low[x], low[y]);
}
else if (i != (from ^ 1))
low[x] = min(low[x], dfn[y]);
}
if (dfn[x] == low[x])
{
int y;
cnt ++ ;
do {
y = stk[tt -- ];
id[y] = cnt;
} while (x != y);
}
}
int main()
{
memset(h, -1, sizeof(h));
scanf("%d%d", &n, &m);
int x, y;
for (int i = 0; i < m; ++ i )
{
scanf("%d%d", &x, &y);
add(x, y), add(y, x);
}
tarjan(1, -1);
for (int x = 1; x <= n; ++ x )
for (int i = h[x]; i != -1; i = ne[i])
{
int y = e[i];
int a = id[x], b = id[y];
if (a != b) d[a] ++ ;
}
int res = 0;
for (int i = 1; i <= cnt; i ++ )
if (d[i] == 1) res ++ ;
if (cnt == 1) puts("0");
else printf("%d\n", (res + 1) / 2);
return 0;
}
1183. 電力
1183. 電力 - AcWing題庫(kù)
枚舉所有割點(diǎn)，判斷刪除哪個(gè)割點(diǎn)后剩余的連通塊數(shù)量最大
剩余的連通塊數(shù)量為ans + cnt - 1
由于題目給定的圖并不是一個(gè)連通圖，所以可能存在多個(gè)連通塊，cnt為連通塊數(shù)量
枚舉所有割點(diǎn)只能在一個(gè)連通塊中枚舉，此時(shí)其他連通塊的數(shù)量為cnt - 1
又因?yàn)閍ns為刪除割點(diǎn)后，剩余連通塊最多的值，所以答案為ans + cnt - 1
這題的點(diǎn)編號(hào)從0開(kāi)始
#include <iostream>
#include <cstring>
using namespace std;
const int N = 10010, M = 30010;
int h[N], e[M], ne[M], idx;
int dfn[N], low[N], tp, cnt;
int ans, n, m, root;
void add(int x, int y)
{
e[idx] = y, ne[idx] = h[x], h[x] = idx ++ ;
}
void tarjan(int x)
{
dfn[x] = low[x] = ++ tp;
int t = 0;
for (int i = h[x]; i != -1; i = ne[i])
{
int y = e[i];
if (!dfn[y])
{
tarjan(y);
low[x] = min(low[x], low[y]);
if (low[y] >= dfn[x]) t ++ ;
}
else low[x] = min(low[x], dfn[y]);
}
if (x != root) t ++ ;
ans = max(ans, t);
}
int main()
{
while (scanf("%d%d", &n, &m), n | m)
{
memset(h, -1, sizeof(h));
memset(dfn, 0, sizeof(dfn));
idx = tp = cnt = ans = 0;
int x, y;
for (int i = 0; i < m; ++ i )
{
scanf("%d%d", &x, &y);
add(x, y), add(y, x);
}
for (root = 0; root < n; ++ root)
{
if (!dfn[root])
{
cnt ++ ;
tarjan(root);
}
}
printf("%d\n", ans + cnt - 1);
}
return 0;
}
debug：dfn數(shù)組沒(méi)有置空
396. 礦場(chǎng)搭建
396. 礦場(chǎng)搭建 - AcWing題庫(kù)
對(duì)于圖中的每個(gè)連通塊，分情況討論：文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-652065.html
- 若連通塊無(wú)割點(diǎn)，那么任意設(shè)置兩個(gè)救援點(diǎn)即可
- 若連通塊中有割點(diǎn)，縮點(diǎn)：將每個(gè)割點(diǎn)依然看成一個(gè)點(diǎn)，將每個(gè)v-DCC向其包含的割點(diǎn)連線
- 縮點(diǎn)后得到一棵樹(shù)，對(duì)于葉子節(jié)點(diǎn)，需要建立救援點(diǎn)。因?yàn)橹挥幸粋€(gè)點(diǎn)與其相連，若該點(diǎn)坍塌，需要在內(nèi)部建立救援點(diǎn)。假設(shè)內(nèi)部節(jié)點(diǎn)數(shù)量為cnt，方案數(shù)為cnt-1個(gè)，去除割點(diǎn)
- 對(duì)于非葉子節(jié)點(diǎn)，無(wú)需建立救援點(diǎn)，因?yàn)闊o(wú)論與之相連的哪個(gè)割點(diǎn)坍塌，該節(jié)點(diǎn)都能走到葉子節(jié)點(diǎn)，而葉子節(jié)點(diǎn)已經(jīng)建立救援點(diǎn)
#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
typedef unsigned long long ULL;
const int N = 1010, M = 1010;
int h[N], e[M], ne[M], idx;
vector<int> dcc[N];
int dcnt, root;
int dfn[N], low[N], tp;
int stk[N], tt;
bool st[N];
int n, m;
void add(int x, int y)
{
e[idx] = y, ne[idx] = h[x], h[x] = idx ++ ;
}
void tarjan(int x)
{
low[x] = dfn[x] = ++ tp;
stk[ ++ tt ] = x;
if (x == root && h[x] == -1)
{
dcnt ++ ;
dcc[dcnt].push_back(x);
return;
}
int t = 0;
for (int i = h[x]; i != -1; i = ne[i])
{
int y = e[i];
if (!dfn[y])
{
tarjan(y);
low[x] = min(low[x], low[y]);
if (low[y] >= dfn[x])
{
t ++, dcnt ++ ;
if (x != root || t > 1) st[x] = true;
int u;
do {
u = stk[tt -- ];
dcc[dcnt].push_back(u);
} while (u != y);
dcc[dcnt].push_back(x);
}
}
else low[x] = min(low[x], dfn[y]);
}
}
int main()
{
int T = 1;
while (scanf("%d", &m), m)
{
for (int i = 0; i < N; ++ i ) dcc[i].clear();
memset(h, -1, sizeof(h));
memset(dfn, 0, sizeof(dfn));
memset(st, false, sizeof(st));
tp = dcnt = idx = tt = n = 0;
for (int i = 0; i < m; ++ i )
{
int x, y;
scanf("%d%d", &x, &y);
add(x, y), add(y, x);
n = max(n, x), n = max(n, y);
}
for (root = 1; root <= n; ++ root )
if (!dfn[root]) tarjan(root);
ULL sum = 1; int ans = 0;
for (int i = 1; i <= dcnt; ++ i )
{
int t = 0;
for (int j = 0; j < dcc[i].size(); ++ j )
if (st[dcc[i][j]])
t ++ ;
if (t == 0)
{
if (dcc[i].size() > 1) ans += 2, sum *= ((ULL)dcc[i].size() * (dcc[i].size() - 1)) / 2;
else ans ++ ;
}
else if (t == 1) ans += 1, sum *= (dcc[i].size() - 1);
}
printf("Case %d: %d %llu\n", T ++ , ans, sum);
}
return 0;
}
debug：由于多組測(cè)試數(shù)據(jù)，沒(méi)有初始化干凈所有元素
最后統(tǒng)計(jì)救援點(diǎn)數(shù)量以及方案總數(shù)時(shí)，沒(méi)有對(duì)孤立點(diǎn)進(jìn)行特判文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-652065.html
到了這里，關(guān)于第三章 圖論 No.10無(wú)向圖的雙連通分量的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
