LeetCode 솔루션 분류

[12/19] 1971. Find if Path Exists in Graph

컨텐츠 정보

본문

There is a bi-directional graph with n vertices, where each vertex is labeled from 0 to n - 1 (inclusive). The edges in the graph are represented as a 2D integer array edges, where each edges[i] = [ui, vi] denotes a bi-directional edge between vertex ui and vertex vi. Every vertex pair is connected by at most one edge, and no vertex has an edge to itself.

You want to determine if there is a valid path that exists from vertex source to vertex destination.

Given edges and the integers nsource, and destination, return true if there is a valid path from source to destination, or false otherwise.

 

Example 1:

<img alt="" src="https://assets.leetcode.com/uploads/2021/08/14/validpath-ex1.png" style="border: 0px none; box-sizing: border-box; --tw-border-spacing-x:0; --tw-border-spacing-y:0; --tw-translate-x:0; --tw-translate-y:0; --tw-rotate:0; --tw-skew-x:0; --tw-skew-y:0; --tw-scale-x:1; --tw-scale-y:1; --tw-pan-x: ; --tw-pan-y: ; --tw-pinch-zoom: ; --tw-scroll-snap-strictness:proximity; --tw-ordinal: ; --tw-slashed-zero: ; --tw-numeric-figure: ; --tw-numeric-spacing: ; --tw-numeric-fraction: ; --tw-ring-inset: ; --tw-ring-offset-width:0px; --tw-ring-offset-color:#fff; --tw-ring-color:rgba(59,130,246,0.5); --tw-ring-offset-shadow:0 0 #0000; --tw-ring-shadow:0 0 #0000; --tw-shadow:0 0 #0000; --tw-shadow-colored:0 0 #0000; --tw-blur: ; --tw-brightness: ; --tw-contrast: ; --tw-grayscale: ; --tw-hue-rotate: ; --tw-invert: ;
태그 ,

관련자료

댓글 2

학부유학생님의 댓글

  • 익명
  • 작성일
from collections import defaultdict
class Solution:
    def validPath(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:

        graph = defaultdict(list)
        for n1, n2 in edges:
            graph[n1].append(n2)
            graph[n2].append(n1)

        visited = set()

        def dfs(node):
            visited.add(node)
            if node == destination:
                return True
            
            res = False
            for nxt in graph[node]:
                if nxt not in visited:
                    res = res or dfs(nxt)
            return res
        return dfs(source)

mingki님의 댓글

  • 익명
  • 작성일
class Solution {
public:
  bool validPath(int n, vector<vector<int>>& edges, int source, int destination) {
    std::vector<std::vector<int>> graph(n, std::vector<int>());
    std::vector<bool> visited(n, 0);

    for (auto &v : edges) {
      graph[v[0]].push_back(v[1]);
      graph[v[1]].push_back(v[0]);
    }
    std::stack<int> st;
    st.push(source);
    while (!st.empty()) {
      int curr = st.top(); st.pop();
      if (curr == destination) {
        return true;
      }
      visited[curr] = true;
      for (auto &node : graph[curr]) {
        if (!visited[node]) {
          st.push(node);
        }
      }
    }
    return false;
  }
};
LeetCode 솔루션 357 / 3 페이지
번호
제목
이름

최근글


인기글


새댓글


Stats


알림 0