摘要: 題目要求統(tǒng)計(jì)一個(gè)平面圖中所有邊數(shù)為k的面的個(gè)數(shù)。應(yīng)該是個(gè)經(jīng)典問題。說說我的算法吧。
枚舉每條邊，做以下的基本步驟。
基本步驟：以這條邊作起始邊，不斷地找下一條“最左轉(zhuǎn)”的邊，并且標(biāo)記每個(gè)點(diǎn)的訪問次數(shù)，直到某個(gè)點(diǎn)第3次被訪問為止。
經(jīng)過這個(gè)步驟之后，得到一個(gè)頂點(diǎn)序列。容易知道，當(dāng)且僅當(dāng)這個(gè)頂點(diǎn)序列是2-重復(fù)（就是形如12341234這樣），并且是逆時(shí)針旋轉(zhuǎn)的，那么就是一個(gè)面。
接下去我們就把所有找到的邊數(shù)為k面進(jìn)行hash去重，就得到答案啦。
貌似我想的這個(gè)算法不夠好，如果有更好的算法，歡迎和我討論。
閱讀全文