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 n
, source
, 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;
}
};