圓方樹(shù)，是解決仙人掌問(wèn)題的實(shí)用方法，假設(shè)最初圖都是圓點(diǎn)，對(duì)于每個(gè)環(huán)新建一個(gè)方點(diǎn)并連接這個(gè)環(huán)上所有圓點(diǎn)，能很好規(guī)避同一個(gè)點(diǎn)可能屬于很多個(gè)環(huán)的情況，并且發(fā)現(xiàn)build完之后是一棵樹(shù)

廣義圓方樹(shù)，能夠不局限于去解決仙人掌問(wèn)題，能上升到無(wú)向圖層面，很好解決圖上路徑類(lèi)，等等問(wèn)題

那么如何建立圓方樹(shù)？有點(diǎn)類(lèi)似 \(v-dcc\) ，建立方點(diǎn)，連接當(dāng)前點(diǎn)雙聯(lián)通分量的所有點(diǎn)，實(shí)現(xiàn)通過(guò)tarjan算法

但注意 \(v-dcc\) 把整個(gè)點(diǎn)雙聯(lián)通分量都縮成一個(gè)點(diǎn)了，圓方樹(shù)還保持著圓點(diǎn)，也就是說(shuō)圓方樹(shù)點(diǎn)數(shù)是 \(n+k\) ，其中 \(k\) 標(biāo)號(hào)是點(diǎn)雙個(gè)數(shù)

具體實(shí)現(xiàn)不詳講，但存在值得注意的細(xì)節(jié)：

令 \(now\) 為當(dāng)前 \(dfs\) 到的節(jié)點(diǎn)， \(y\) 為其搜索樹(shù)上的一個(gè)兒子。注意， \(now\) 與 \(y\) 在棧中不一定相鄰。也就是說(shuō)，下面兩種寫(xiě)法：

1. 彈出棧頂直到彈出 \(now\) 為止；最后再壓入 \(now\)
2. 彈出棧頂直到彈出 \(y\) 為止，最后再將虛點(diǎn)向 \(now\) 連邊
   前者錯(cuò)誤，后者正確。

代碼：

void tarjan(int x){
	++nown;
	dfn[x]=low[x]=++num;
	st.push(x),w[x]=-1; 
	for(int i=head[x];i;i=edge[i].Next){
		int to=edge[i].to;
		if(!dfn[to]){
			tarjan(to);
			low[x]=min(low[x],low[to]);
			if(low[to]>=dfn[x]){
			    addedge2(++diannum,x),addedge2(x,diannum);
				++w[diannum];
				while(1){
					addedge2(diannum,st.top()),addedge2(st.top(),diannum);
					++w[diannum];
					if(st.top()==to){
						st.pop();
						break;
					}
					st.pop();
				}
			}
		}
		else low[x]=min(low[x],dfn[to]);				
	}
}

\(v-dcc\) 和圓方樹(shù)運(yùn)用區(qū)別何在？后者對(duì)于點(diǎn)雙內(nèi)部的處理能夠非常方便，而前者似乎處理整個(gè)點(diǎn)雙對(duì)答案的貢獻(xiàn)（不考慮單點(diǎn)）會(huì)十分好搞

圓方樹(shù)的性質(zhì)：

1. 是樹(shù)

2. 每條邊都是方點(diǎn)和圓點(diǎn)連接邊

3. 每個(gè)方點(diǎn)對(duì)應(yīng)一個(gè)點(diǎn)雙聯(lián)通分量

4. 方點(diǎn)的度數(shù)是點(diǎn)雙聯(lián)通分量的大小

5. 圓點(diǎn)是割點(diǎn)才有超過(guò)1個(gè)兒子，否則只連接一個(gè)方點(diǎn)兒子

6. 圓方樹(shù)上兩個(gè)點(diǎn)的路徑經(jīng)過(guò)的圓點(diǎn)是圖上兩點(diǎn)之間的必經(jīng)點(diǎn)

還有一些點(diǎn)雙的小性質(zhì)：對(duì)于一個(gè)點(diǎn)雙的兩點(diǎn)，它們之間簡(jiǎn)單路徑的并集等于這個(gè)點(diǎn)雙集合

圓方樹(shù)能夠很好地將無(wú)向圖上問(wèn)題轉(zhuǎn)化為樹(shù)上問(wèn)題，進(jìn)行統(tǒng)計(jì)類(lèi)的時(shí)候可能割點(diǎn)會(huì)被統(tǒng)計(jì)多次，所有一般把方點(diǎn)賦為-1，然后就很好做了，等等就不細(xì)說(shuō)了

總結(jié)

以上是生活随笔為你收集整理的圆方树 useful things的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。