生活随笔
收集整理的這篇文章主要介紹了
模板：圆方树
小編覺得挺不錯的,現(xiàn)在分享給大家,幫大家做個參考.
所謂圓方樹，就是又圓又方的樹
（逃）
前言
樹有很多良好的性質(zhì)，也可以上許多算法和數(shù)據(jù)結(jié)構(gòu)
但我們對于一般圖卻沒有太多辦法…
然而，對于有些關(guān)注連同性、路徑并&交的一般圖問題，我們可以用圓方樹，轉(zhuǎn)化為樹上問題解決。
解析
簡介
把所有的點雙求出來，然后把每個點雙建成一個點（稱為方點），向點雙內(nèi)的所有點（稱為圓點）連邊
實現(xiàn)
既然要求點雙，當然要用tarjan啦
和普通的求tarjan求割點有一些區(qū)別：（越來越容易掛了）
不需要在函數(shù)里特判根（但是最后需要把殘留在棧里的根彈掉）求出點雙彈棧時son和x不一定在棧里是相鄰的（其實比較顯然）
void tarjan(int x
){dfn
[x
]=low
[x
]=++tim
;zhan
[++top
]=x
;for(int i
=g1
.fi
[x
];~i
;i
=g1
.p
[i
].nxt
){int to
=g1
.p
[i
].to
;if(!dfn
[to
]){tarjan(to
);low
[x
]=min(low
[x
],low
[to
]); if(low
[to
]==dfn
[x
]){++tot
;g2
.addline(tot
,x
);g2
.addline(x
,tot
);while(zhan
[top
]!=to
){int now
=zhan
[top
--];++val
[tot
];g2
.addline(now
,tot
);g2
.addline(tot
,now
);}int now
=to
;++val
[tot
];g2
.addline(now
,tot
);g2
.addline(tot
,now
);top
--;}}else low
[x
]=min(low
[x
],dfn
[to
]);}return;
}
創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅持創(chuàng)作打卡瓜分現(xiàn)金大獎
總結(jié)
以上是生活随笔為你收集整理的模板：圆方树的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。
