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