Q: http://poj.org/problem?id=1635

 

給定2個tree, 判斷這兩個tree是否為isomorphism

也就是說是否為同樣的架構(不用看值,直接看"架構"就好)

 

解題的方法很特殊,是用hash的方式去計算單一一個tree的id

如果算出來的id相同,則代表2棵樹的架構一樣,是為isomorphism

 

先根據input利用vector來建立tree

之後利用遞迴的方法計算root的hash值

如果遇到葉節點就直接回傳一個自己設好的質數(這裡設成191)

hash function為HASH(node) = (HASH(child)^2的總和) mod  34943

 

可能是因為我沒有建表把每個node的hash值記錄下來吧

速度有點慢,不過還是過了=w=

 

 

一開始跑起來結果還怪怪的

之後才發現原來我沒有吸收換行

導致input錯誤,連帶造成答案怪怪的

要細心一點啊@@

arrow
arrow
    文章標籤
    ACM POJ STL Tree Isomorphism 程式
    全站熱搜

    Tube 發表在 痞客邦 留言(0) 人氣()

    E-mail轉寄