Skip to main content

1971. Find if Path Exists in Graph - LeetCode

ยท One min read
from collections import deque

vertexT = int


class Solution1:
# [dfs] Runtime 2560 ms Beats 7.20%
def validPath(
self, n: int, edges: list[list[int]], source: int, destination: int
) -> bool:
graph: dict[vertexT, list[vertexT]] = {}
for vertex_1, vertex_2 in edges:
graph.setdefault(vertex_1, []).append(vertex_2)
graph.setdefault(vertex_2, []).append(vertex_1)

visiteds: set[vertexT] = set()

def dfs(vertex: vertexT):
if vertex == destination:
return True
if vertex in visiteds:
return False
visiteds.add(vertex)
return any(map(dfs, graph[vertex]))

return dfs(source)


class Solution2:
# [bfs] Runtime 1971 ms Beats 61.44%
def validPath(
self, n: int, edges: list[list[int]], source: int, destination: int
) -> bool:
graph: dict[vertexT, set[vertexT]] = {}
for vertex_1, vertex_2 in edges:
graph.setdefault(vertex_1, set()).add(vertex_2)
graph.setdefault(vertex_2, set()).add(vertex_1)

visiteds: set[vertexT] = set()
queue: deque[set[vertexT]] = deque([{source}])
while queue:
next_: set[vertexT] = set()
q = queue.popleft()
for vertex in q:
if vertex == destination:
return True
if vertex in visiteds:
continue
visiteds.add(vertex)
next_ |= graph[vertex]
if next_:
queue.append(next_)
return False


class Uf3:
def __init__(self, root: dict[vertexT, vertexT]):
self.root = root

def find(self, x: vertexT):
if x not in self.root:
self.root[x] = x
if self.root[x] != x:
self.root[x] = self.find(self.root[x])
return self.root[x]

def union(self, x: vertexT, y: vertexT):
x_root, y_root = self.find(x), self.find(y)
self.root[x_root] = y_root


class Solution3:
# [uf]
def validPath(
self, n: int, edges: list[list[int]], source: int, destination: int
) -> bool:
uf = Uf3({})
for x, y in edges:
uf.union(x, y)
return uf.find(source) == uf.find(destination)


class Uf4:
def __init__(self, root: dict[vertexT, vertexT]):
self.root = root

def find(self, x: vertexT):
# [iteratively]
if x not in self.root:
self.root[x] = x
while self.root[x] != x:
self.root[x] = self.root[self.root[x]]
x = self.root[x]
return self.root[x]

def union(self, x: vertexT, y: vertexT):
x_root, y_root = self.find(x), self.find(y)
self.root[x_root] = y_root


class Solution4:
def validPath(
self, n: int, edges: list[list[int]], source: int, destination: int
) -> bool:
uf = Uf4({})
for x, y in edges:
uf.union(x, y)
return uf.find(source) == uf.find(destination)


class Uf5:
def __init__(self, root: dict[vertexT, vertexT]):
self.root = root

def find(self, x: vertexT):
# dict.setdefault
if self.root.setdefault(x, x) != x:
self.root[x] = self.find(self.root[x])
return self.root[x]

def union(self, x: vertexT, y: vertexT):
x_root, y_root = self.find(x), self.find(y)
self.root[x_root] = y_root


class Solution5:
def validPath(
self, n: int, edges: list[list[int]], source: int, destination: int
) -> bool:
uf = Uf5({})
for x, y in edges:
uf.union(x, y)
return uf.find(source) == uf.find(destination)


class Uf6:
DUMMY_VERTEX = -1

def __init__(self, root: list[vertexT]):
# use `list`
self.root = root

def find(self, x: vertexT):
if self.root[x] is self.DUMMY_VERTEX:
self.root[x] = x
if self.root[x] != x:
self.root[x] = self.find(self.root[x])
return self.root[x]

def union(self, x: vertexT, y: vertexT):
x_root, y_root = self.find(x), self.find(y)
self.root[x_root] = y_root


class Solution6:
def validPath(
self, n: int, edges: list[list[int]], source: int, destination: int
) -> bool:
uf = Uf6(list(range(n)))
for x, y in edges:
uf.union(x, y)
return uf.find(source) == uf.find(destination)


class Uf7:
def __init__(self, root: list[vertexT]):
self.root = root

def find(self, x: vertexT):
# without dummy (run union)
if self.root[x] != x:
self.root[x] = self.find(self.root[x])
return self.root[x]

def union(self, x: vertexT, y: vertexT):
x_root, y_root = self.find(x), self.find(y)
self.root[x_root] = y_root


class Solution7:
def validPath(
self, n: int, edges: list[list[int]], source: int, destination: int
) -> bool:
uf = Uf7(list(range(n)))
for x, y in edges:
uf.union(x, y)
return uf.find(source) == uf.find(destination)