觀前須知
筆者的博客主頁(yè)
聲明
本文使用 CC BY-NC-SA 4.0 許可。
本文為筆者在 OI 學(xué)習(xí)中的復(fù)習(xí)向?qū)W習(xí)筆記。
部分內(nèi)容會(huì)比較簡(jiǎn)略。
如有好的習(xí)題會(huì)不斷補(bǔ)充。
知識(shí)簡(jiǎn)介
定義
基環(huán)樹是一個(gè)有 \(n\) 個(gè)點(diǎn) \(n\) 條邊的連通圖。
因?yàn)?strong>樹有 \(n\) 個(gè)點(diǎn) \(n-1\) 條邊。
所以基環(huán)樹可以看作是加了一條邊的樹。
那么也就是加了個(gè)環(huán)的樹。
注意：題目中給 \(n\) 點(diǎn) \(n\) 邊時(shí)可能是基環(huán)樹，也可能是基環(huán)樹森林。
后一種情況分連通分量分別做即可。
如圖：
拓?fù)渑判蛘噎h(huán)
無(wú)向圖：
不斷地刪除 1 度點(diǎn)，直到留下的全部都是 2 度點(diǎn)，即為環(huán)。
有向圖：
同上，只不過(guò)每次刪入度為 0 的點(diǎn)。
DFS找環(huán)
無(wú)向圖：
走的時(shí)候記 dfn 和 fa，
遇到遍歷過(guò)且 dfn 大的點(diǎn)（防止重復(fù)計(jì)算），
就不斷跳 fa 并記錄。
代碼：
void Dfs(int u) {
dfn[u] = ++Time;
for (int i = head[u]; i; i = e[i].nxt) {
int v = e[i].v;
if (v == fa[u]) continue;
if (!dfn[v]) { fa[v] = u, Dfs(v); }
else {
if (dfn[v] < dfn[u]) continue;
loop[++cnt] = v;
while (v != u) loop[++cnt] = v = fa[v];
}
}
}
有向圖：
如果邊指向葉子可以反過(guò)來(lái)。
邊指向根的樹只需要不斷向上跳 fa，同時(shí)打標(biāo)記，
直到跳到樹的根后，再跳到的點(diǎn)已經(jīng)打過(guò)標(biāo)記了，那么就找到環(huán)了。
（如果要樹型DP的話可以再建個(gè)反向圖，就不用建雙向圖了）
代碼：
while (!vis[x]) vis[x] = true, x = fa[x];
int v = x;
while (v != x) loop[++cnt] = v = fa[v];
基環(huán)樹常見(jiàn)問(wèn)題處理方式
把環(huán)斷開，發(fā)現(xiàn)圖變成了若干個(gè)森林。
那么可以把基環(huán)樹看作用一個(gè)環(huán)連接著的若干棵樹。
這時(shí)候就可以先斷環(huán)，然后再樹型DP了。
特別地，有些題涉及到樹之間經(jīng)過(guò)環(huán)的轉(zhuǎn)移。
這類問(wèn)題可以分類討論成不經(jīng)過(guò)環(huán)的和經(jīng)過(guò)環(huán)的分別處理。
由于有環(huán)的出現(xiàn)，破環(huán)為鏈也比較常用。文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-844408.html
習(xí)題
Luogu P2607 【ZJOI2008】 騎士
首先這個(gè)東西顯然可以樹型DP做。
但是這里是個(gè)基環(huán)樹森林。
發(fā)現(xiàn)對(duì)于環(huán)的任意兩個(gè)相鄰點(diǎn)只能二選一或都不選。
那么任取環(huán)上的兩個(gè)點(diǎn)分別做樹型dp取 \(\max(f_{u_1,0},f_{u_2,0})\)，然后對(duì)每個(gè)基環(huán)樹求和即可。文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-844408.html
到了這里，關(guān)于關(guān)于基環(huán)樹的一切的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
