1971. Find if Path Exists in Graph LeetCode Solution
In this guide, you will get 1971. Find if Path Exists in Graph LeetCode Solution with the best time and space complexity. The solution to Find if Path Exists in Graph problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
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:
Input: n = 3, edges = [[0,1],[1,2],[2,0]], source = 0, destination = 2
Output: true
Explanation: There are two paths from vertex 0 to vertex 2:
– 0 → 1 → 2
– 0 → 2
Example 2:
Input: n = 6, edges = [[0,1],[0,2],[3,5],[5,4],[4,3]], source = 0, destination = 5
Output: false
Explanation: There is no path from vertex 0 to vertex 5.
1 <= n <= 2 * 105
0 <= edges.length <= 2 * 105
edges[i].length == 2
0 <= ui, vi <= n – 1
ui != vi
0 <= source, destination <= n – 1
There are no duplicate edges.
There are no self edges.
Complexity Analysis
Time Complexity:
Space Complexity:
1971. Find if Path Exists in Graph LeetCode Solution in C++
class UnionFind {
public:
UnionFind(int n) : id(n), rank(n) {
iota(id.begin(), id.end(), 0);
}
void unionByRank(int u, int v) {
const int i = find(u);
const int j = find(v);
if (i == j)
return;
if (rank[i] < rank[j]) {
id[i] = j;
} else if (rank[i] > rank[j]) {
id[j] = i;
} else {
id[i] = j;
++rank[j];
}
}
int find(int u) {
return id[u] == u ? u : id[u] = find(id[u]);
}
private:
vector<int> id;
vector<int> rank;
};
class Solution {
public:
bool validPath(int n, vector<vector<int>>& edges, int source,
int destination) {
UnionFind uf(n);
for (const vector<int>& edge : edges) {
const int u = edge[0];
const int v = edge[1];
uf.unionByRank(u, v);
}
return uf.find(source) == uf.find(destination);
}
}; /* code provided by PROGIEZ */
1971. Find if Path Exists in Graph LeetCode Solution in Java
class UnionFind {
public UnionFind(int n) {
id = new int[n];
rank = new int[n];
for (int i = 0; i < n; ++i)
id[i] = i;
}
public void unionByRank(int u, int v) {
final int i = find(u);
final int j = find(v);
if (i == j)
return;
if (rank[i] < rank[j]) {
id[i] = j;
} else if (rank[i] > rank[j]) {
id[j] = i;
} else {
id[i] = j;
++rank[j];
}
}
public int find(int u) {
return id[u] == u ? u : (id[u] = find(id[u]));
}
private int[] id;
private int[] rank;
}
class Solution {
public boolean validPath(int n, int[][] edges, int source, int destination) {
UnionFind uf = new UnionFind(n);
for (int[] edge : edges) {
final int u = edge[0];
final int v = edge[1];
uf.unionByRank(u, v);
}
return uf.find(source) == uf.find(destination);
}
} // code provided by PROGIEZ
1971. Find if Path Exists in Graph LeetCode Solution in Python
class UnionFind:
def __init__(self, n: int):
self.id = list(range(n))
self.rank = [0] * n
def unionByRank(self, u: int, v: int) -> None:
i = self.find(u)
j = self.find(v)
if i == j:
return
if self.rank[i] < self.rank[j]:
self.id[i] = j
elif self.rank[i] > self.rank[j]:
self.id[j] = i
else:
self.id[i] = j
self.rank[j] += 1
def find(self, u: int) -> int:
if self.id[u] != u:
self.id[u] = self.find(self.id[u])
return self.id[u]
class Solution:
def validPath(
self,
n: int,
edges: list[list[int]],
source: int,
destination: int,
) -> bool:
uf = UnionFind(n)
for u, v in edges:
uf.unionByRank(u, v)
return uf.find(source) == uf.find(destination) # code by PROGIEZ
