[問題] leetcode 2029 (Hard) 的問題

[VivianAnn (薇薇安安)]

不知這裡有沒有高手有參加這週的Leetcode 週賽，想請教leetcode 2029

https://leetcode.com/problems/find-all-people-with-secret/

這題我是用Union-Find來做的，思路大致是：


先用一個dictionary把同一個時間的meeting放在一起，然後由時間小的loop到時間大的

如果該meeting中的參與人x, y中有一個和firstPerson是同一個根節點，則union

在每一個union操作後，將x, y皆放入res

同個時間若有多個meeting，則用一個while loop，不斷檢查該時間的所有x, y組合

直至res不再變動


以下是我的code，我一直想不透錯在哪，到第38個test case時fail了


class Solution(object):
    def findAllPeople(self, n, meetings, firstPerson):
        """
        :type n: int
        :type meetings: List[List[int]]
        :type firstPerson: int
        :rtype: List[int]
        """
        parent = {i: i for i in range(n)}

        res = set()

        res.add(0)
        res.add(firstPerson)

        def find(x):
            if x != parent[x]:
                parent[x] = find(parent[x])
            return parent[x]

        def union(a, b):
            pa, pb = find(a), find(b)
            if pa!=pb:
                parent[pa] = pb

        union(0, firstPerson)

        hmap = collections.defaultdict(list)

        for a, b, time in meetings:
            hmap[time].append((a, b))

        for time in sorted(hmap.keys()):
            arr = hmap[time]
            while True:
                tmp = res
                for a, b in arr:
                    if find(a) == find(firstPerson) or find(b) ==
find(firstPerson):
                        union(a,b)
                        res.add(a)
                        res.add(b)
                if tmp == res:
                    break

        return list(res)


感謝各位願意看完

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 108.254.89.199 (美國)
※ 文章網址: https://www.ptt.cc/bbs/Python/M.1638136732.A.669.html
推 s0914714: 我猜是find(a) == find(firstPerson) or find(b)...這行
→ s0914714: 有可能迭代還沒完成但是tmp等於res
推 s0914714: 我是用一個set紀錄find(a), find(b)跟find(firstPerson)
→ s0914714: 每次循環結束檢查set長度，如果沒變就能跳出
→ VivianAnn: 問下，有可能迭代沒完成但res = tmp 嗎?
推 s0914714: 後來find的節點有機會讓之前find過的節點變更parent
→ s0914714: 最簡單的方式就是你的while True改成count跑個5次試試
推 s0914714: 不要tmp == res就break
→ VivianAnn: 查出問題了，tmp = res.copy()才對，不過會TLE
推 s0914714: 都忘了set也是淺拷貝XD
→ s0914714: 你的res會越來越大 TLE很正常吧
→ s0914714: 改成記長度之類的
推 s0914714: 有可能迭代沒完成但res = tmp 嗎? =>我想錯了 這不可能
推 cuteSquirrel: 提示: 同一個時段舉行的meeting仍然會洩漏秘密
推 cuteSquirrel: 提供一組測資，幫助你用來除錯。
→ cuteSquirrel:  http://codepad.org/RmBe4P91
推 cuteSquirrel: 留意這段敘述 https://i.imgur.com/rycNcnU.png
推 s0914714: 不過原PO會把答案加到res 後面的人知道秘密就會加入res
→ s0914714: 所以res就跟一開始不一樣
→ VivianAnn: 謝謝，我已經懂了
→ VivianAnn: 這題蠻好的，值得一做