• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            Uriel's Corner

            Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
            posts - 0, comments - 50, trackbacks - 0, articles - 594
            給出一個無向圖(給定節點數、所有的邊),問是否存在連接起點到終點的路,簡單DFS,用set記錄訪問過的節點(改為記錄訪問過的邊會TLE)

            寫法一,DFS完判定終點是否到達過

             1 #1971
             2 #Runtime: 3120 ms (Beats 67.40%)
             3 #Memory: 348.8 MB (Beats 5.11%)
             4 
             5 class Solution(object):
             6     def validPath(self, n, edges, source, destination):
             7         """
             8         :type n: int
             9         :type edges: List[List[int]]
            10         :type source: int
            11         :type destination: int
            12         :rtype: bool
            13         """
            14         graph_dict = defaultdict(set)
            15         vis = set()
            16         for x, y in edges:
            17             graph_dict[x].add(y)
            18             graph_dict[y].add(x)
            19 
            20         def DFS(t, des):
            21             vis.add(t)
            22             if t == des:
            23                 return
            24             if t in graph_dict:
            25                 for j in graph_dict[t]:
            26                     if j not in vis:
            27                         DFS(j, des)
            28         DFS(source, destination)
            29         return destination in vis

            寫法二,DFS過程中直接判False或者True,不知為何此種寫法慢一些

             1 #1971
             2 #Runtime: 4947 ms (Beats 17.28%)
             3 #Memory: 353 MB (Beats 5.11%)
             4 
             5 class Solution(object):
             6     def validPath(self, n, edges, source, destination):
             7         """
             8         :type n: int
             9         :type edges: List[List[int]]
            10         :type source: int
            11         :type destination: int
            12         :rtype: bool
            13         """
            14         graph_dict = defaultdict(set)
            15         vis = set()
            16         for x, y in edges:
            17             graph_dict[x].add(y)
            18             graph_dict[y].add(x)
            19 
            20         def DFS(t, des):
            21             vis.add(t)
            22             if t == des:
            23                 return True
            24             if t in graph_dict:
            25                 for j in graph_dict[t]:
            26                     if j not in vis and DFS(j, des):
            27                         return True
            28             return False
            29         return DFS(source, destination)
            30         



            国产呻吟久久久久久久92| 韩国三级大全久久网站| 国产精品久久新婚兰兰| 亚洲国产精品无码久久久不卡| 久久人人妻人人爽人人爽| 大伊人青草狠狠久久| 色8激情欧美成人久久综合电| 久久伊人五月天论坛| 亚洲精品乱码久久久久久自慰| 日韩精品无码久久久久久| 91精品无码久久久久久五月天 | 一级a性色生活片久久无| 久久人人爽人人人人片av| 久久99精品久久久久久久久久| 久久久久亚洲AV综合波多野结衣| 久久婷婷人人澡人人爽人人爱| 狠狠狠色丁香婷婷综合久久俺| 久久久久国色AV免费看图片| 久久夜色精品国产噜噜噜亚洲AV| 激情五月综合综合久久69| 久久久久亚洲精品无码蜜桃| 亚洲精品高清一二区久久| 99久久国产综合精品成人影院 | 精品国产91久久久久久久a| 亚洲伊人久久精品影院 | 国色天香久久久久久久小说| 久久久久国产日韩精品网站| 久久国产免费观看精品| 久久精品国产亚洲AV无码娇色| 亚洲精品第一综合99久久 | 中文字幕人妻色偷偷久久| 久久综合精品国产一区二区三区 | 91精品国产综合久久久久久| 久久精品国产99久久久古代| 一本久久综合亚洲鲁鲁五月天亚洲欧美一区二区 | 久久青青草原综合伊人| 久久久久人妻一区二区三区vr| 午夜天堂av天堂久久久| 亚洲AV日韩精品久久久久 | 久久最新精品国产| 一本大道久久a久久精品综合|