• <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         



            久久中文骚妇内射| 亚洲美日韩Av中文字幕无码久久久妻妇 | 91精品国产高清久久久久久国产嫩草 | 99久久精品费精品国产一区二区| 亚洲AV日韩精品久久久久久| 国产精品99久久精品| 久久综合五月丁香久久激情| 精品多毛少妇人妻AV免费久久| 69久久精品无码一区二区| 久久综合视频网站| 久久线看观看精品香蕉国产| 国产免费久久精品99re丫y| 精品久久久久久亚洲精品| 蜜桃麻豆www久久国产精品| 国产精品久久久久久影院| 久久久久亚洲av成人网人人软件| 精品亚洲综合久久中文字幕| 久久久久人妻一区二区三区 | 国产激情久久久久影院| 99久久国产精品免费一区二区 | 亚洲国产精品18久久久久久| 国产三级精品久久| 97久久精品无码一区二区| 婷婷久久五月天| 久久人人爽人爽人人爽av| 99久久中文字幕| 久久精品国产亚洲AV无码麻豆| 无码人妻少妇久久中文字幕| 中文精品久久久久国产网址| 99re这里只有精品热久久| 久久久久亚洲AV成人片| 乱亲女H秽乱长久久久| 精品久久亚洲中文无码| 伊人色综合九久久天天蜜桃| 久久婷婷五月综合成人D啪 | 91久久精品91久久性色| 久久久国产乱子伦精品作者| 日产精品久久久久久久| 亚洲AV成人无码久久精品老人| 一本色道久久综合亚洲精品| 亚洲va国产va天堂va久久|