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