//Solution is same as BFS only . Just convert 2D vector to adj list and at last check check node visited or not. bool validPath(int n, vector& edges, int source, int destination) {
Tried after the knowing logic . Able to code it myself 🙏 class Solution { public: bool validPath(int n, vector& edges, int source, int destination) { // base case if(edges.size() == 0){ return true; }
// step 1 : creating the adjustant list from edges unordered_map adjList;
Randomly came upon your channel while understanding graphs . But really you're playlist is actually helpful . I am able to solve this without looking at this solution because of your previous videos in the playlist . Thank you Prince for your efforts . Keep growing !
//Solution using converting edges into adjacency list and then traversing the list and marking the visited , and at last checking the destination visited or not. bool validPath(int n, vector& edges, int source, int destination) { vector adj[n]; for(int i=0;i
//Thankyou Bhaiya ..BFS and DFS was like a nightmare to me . Finally able tocode it myself in one go becuase of you . Thankyou so much!! class Solution { public:
int BFS(int n, unordered_map m, int s, int d){ int arr[n]; memset(arr, 0, sizeof(arr)); queue q; q.push(s); arr[s]=1;
while(!q.empty()){ int temp=q.front(); q.pop(); arr[temp]=1; for(int j=0; j
Hey Prince, really nice video. class Solution { public: bool validPath(int n, vector& edges, int source, int destination) { std::vector adj[n]; for (auto& x : edges) { adj[x[0]].push_back(x[1]); adj[x[1]].push_back(x[0]); } std::vector visited(n + 1, false); std::queue q; visited[source] = true; q.push(source); while (!q.empty()) { int u = q.front(); q.pop(); if (u == destination) return true; for (auto x : adj[u]) { if (visited[x]) continue; visited[x] = true; q.push(x); } } return false; } }; I think this will be a lot faster and memory efficient.
its a kind of thinking that if you have some extra space for some edge cases that will be helpful ... still its not always necessary you can most of the time use only 'n' but as a built habit we used generally n+1
Bhaiya mein apne se try kiya but thora error rehe gaya bool validPath(int n, vector& edges, int source, int destination) { unordered_map umap; for (auto x : edges){ vector temp = x; int u = temp[0]; int v = temp[1]; umap[u].push_back(v); umap[v].push_back(u); } vector vis(n, false); queue q; vis[source] = true; q.push(source); while (!q.empty()){ int node = q.front(); q.pop(); for (auto x : umap){ vector temp1 = x.second; for (auto z : temp1){ if (vis[z] == false){ vis[z] = true; q.push(z); } } } } return vis[destination]; }
Thank You :) Tried after the knowing logic . Able to code it myself class Solution { public: bool validPath(int n, vector& p, int source, int destination) { if(destination==source) return true; unordered_mapm; for (int i=0;i
#Python Solution def validPath(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool: if not edges: return True from collections import defaultdict visited = [False]*(n+1) count=-1 def _bfs(arr,i): q = [] q.append(i) visited[i]=True while(len(q)>0): temp = q.pop(0) for v in arr[temp]: if not visited[v]: q.append(v) visited[v]=True dic = defaultdict(list) for a,b in edges: dic[a].append(b) dic[b].append(a) for i in range(len(dic)): if not visited[i]: count+=1 _bfs(dic,i) # print(visited,count) if visited[destination] and count
--------------------------------------------CODE-------------------------------------- class Solution { public: bool validPath(int n, vector& edges, int s, int destination) { vector visited(n+1, false);
than that might be the case of directed graph or that will the adj list only. if not ,than left to right and make a map ,then traverse right to left again do same thing(you can do both in 1 loop) tc - n^2
can we use array inplace of umap like this bool validPath(int n, vector& edges, int source, int destination) { vector adj(n + 1); for (auto x : edges) { int u = x[0]; int v = x[1]; adj[u].push_back(v); adj[v].push_back(u); } vector visited(n + 1, false); queue q; q.push(source); visited[source] = true; while (!q.empty()) { int v = q.front(); q.pop(); for (auto x : adj[v]) { // Traverse the neighbors of the current vertex if (visited[x] == false) { visited[x] = true; q.push(x); } } } return visited[destination]; }
class Solution { public: bool validPath(int n, vector& edges, int source, int destination) { unordered_map ump; for (auto x : edges) { int u = x[0]; int v = x[1]; ump[u].push_back(v); ump[v].push_back(u); } vector visited(n, false); queue q; q.push(source); visited[source] = true; while (!q.empty()) { int res = q.front(); q.pop(); for(int x:ump[res]){ if (visited[x] == false) { q.push(x); visited[x] = true; } } if (visited[destination]) return visited[destination]; } return visited[destination]; } }; vai maine e code kya iska time or space memory bhi bohot kam hua tha.please vai batana mera code thik hai kya nahi
stumbled upon this channel while learning graphs, really great channel!
Please, if possible then share this channel in your college, groups, or LinkedIn bcoz it's cost nothing to you 😀
//Solution is same as BFS only . Just convert 2D vector to adj list and at last check check node visited or not.
bool validPath(int n, vector& edges, int source, int destination) {
vector adj[n];
for (const auto& edge : edges) {
adj[edge[0]].push_back(edge[1]);
adj[edge[1]].push_back(edge[0]);
}
vector vis(n,0);
bfs(n,source,vis,adj);
return vis[destination]?1:0;
}
Tried after the knowing logic . Able to code it myself 🙏
class Solution {
public:
bool validPath(int n, vector& edges, int source, int destination) {
// base case
if(edges.size() == 0){
return true;
}
// step 1 : creating the adjustant list from edges
unordered_map adjList;
// no of edges
int m = edges.size();
// making adjustant list
for(int i=0;i
Waooooo amazing
Randomly came upon your channel while understanding graphs . But really you're playlist is actually helpful . I am able to solve this without looking at this solution because of your previous videos in the playlist . Thank you Prince for your efforts . Keep growing !
explanation sunne ke baad apne aap hei code krdia bhaiya maza a gya 😅😎
Wahhh ...bhut sahi
Mai nhi utha rha tha pen copy 😂
But fir khud solve krke hi bapas aya bhaiya😊❤
prince bhai ap kamaal ho yaar ,u make understand very easily,TAKE A BOW
Thanks buddy
Very nice video! 😊
I think best thing is we should convert the edge list to adjacency list and then we could apply our standard BFS algorithm.
Totally agree!
Best Channel for Learning Graphs
Thanks a ton
Bhiya aap motivate bahot krte ho🙏. Waise maine bahot try kiya kudh se nhi ho rha.
Good things always takes times
//Solution using converting edges into adjacency list and then traversing the list and marking the visited , and at last checking the destination visited or not.
bool validPath(int n, vector& edges, int source, int destination) {
vector adj[n];
for(int i=0;i
Wahhhh gajab 🔥
bhot accha solution hai bhai ...maja aya
Great approch
edges[i][0] and edges[i][1] jo kia h aapne isme dikkat nii aaegi agr 2 se jyda node connected ho ?
class Solution {
public boolean validPath(int n, int[][] edges, int source, int destination) {
if(source==destination){ return true;}
HashMap hm=new HashMap();
for(int e[]:edges){
hm.putIfAbsent(e[0],new ArrayList());
hm.putIfAbsent(e[1],new ArrayList());
hm.get(e[0]).add(e[1]);
hm.get(e[1]).add(e[0]);
}
boolean vis[]=new boolean[n];
help(edges[0][0],hm, edges, vis);
return vis[destination] && vis[source];
}
public void help(int st, HashMap hm, int[][] edges, boolean vis[]){
if(!hm.containsKey(st) || vis[st]){
return; }
vis[st]=true;
for(int l:hm.get(st)){
help(l,hm, edges, vis); }
}
}
Thanks
very helpful on graph Journey
//Thankyou Bhaiya ..BFS and DFS was like a nightmare to me . Finally able tocode it myself in one go becuase of you . Thankyou so much!!
class Solution {
public:
int BFS(int n, unordered_map m, int s, int d){
int arr[n];
memset(arr, 0, sizeof(arr));
queue q;
q.push(s);
arr[s]=1;
while(!q.empty()){
int temp=q.front();
q.pop();
arr[temp]=1;
for(int j=0; j
Hey Prince, really nice video.
class Solution {
public:
bool validPath(int n, vector& edges, int source, int destination)
{
std::vector adj[n];
for (auto& x : edges)
{
adj[x[0]].push_back(x[1]);
adj[x[1]].push_back(x[0]);
}
std::vector visited(n + 1, false);
std::queue q;
visited[source] = true;
q.push(source);
while (!q.empty())
{
int u = q.front();
q.pop();
if (u == destination)
return true;
for (auto x : adj[u])
{
if (visited[x])
continue;
visited[x] = true;
q.push(x);
}
}
return false;
}
};
I think this will be a lot faster and memory efficient.
you teach very well🙌
Thank you! 😃
Thankyou bhaiya! very helpful video 🙏
thanks bhaiya for inspiring to try on our own
HERE IS THE COMPLETE CODE:
class Solution {
public:
bool validPath(int n, vector& edges, int source, int destination) {
//edges to adjacency list
vector list(n);
for(auto x: edges)
{
int u = x[0];
int v = x[1];
list[u].push_back(v);
list[v].push_back(u);
//list[x[0]].push_back(x[1]);
// list[x[1]].push_back(x[0]);
}
if(source==destination){
//cout
3:45 bhaiya is it unordered map or adjacency matrix?
isme edges adjacency list hai kya ???
Amazing Astha.. keep learning buddy
and why u didn't came in last live session ?
After seeing your video I feel very confident because my run time is very high 200ms that means we cannot solve graph problems at 1 or 2 ms
Waoooooooo Amazing
bhaiyaa vector adjlist[n] bhi bna skte h n umap ki jgh ?
7:14 done bhaiya
Niceee
my age 35 years old but programing bahut pasand hai mera
I attempted this question 👌
amazing keep learning
bool validPath(int n, vector& edges, int start, int end) {
vector graph(n);
// Build the graph
for(int i=0; i
//JAVA Solution
class Solution {
public boolean validPath(int n, int[][] edges, int source, int destination) {
HashMap hm = new HashMap();
if(source==destination) return true;
for(int i=0;i
darkar? hindi shabdkosh leke baithna padega. Dhanyavvvad sikhsha vayam. 🙏🙏
class Solution {
public:
void BFS( vector adj[], int source, vector &visited ){
queue q;
q.push(source); visited[source]=1;
while( !q.empty() ){
int curr = q.front();
q.pop();
for( auto x:adj[curr] ){
if( visited[x] == 0 ){
visited[x] = 1;
q.push(x);
}
}
}
return;
}
bool validPath(int n, vector& edges, int source, int destination) {
int v=edges.size();
vector adj[n];
if(v==0){
return true;
}
for( int i=0 ; i
good work brother
what is the meaning of this vector& edges
isn't it in the form of adjacency list?
yess it is
Do bfs and if front==destination return true, after full traversal if we did not get front==destination then return false
3:24 are bhaiya aapne mera webcam to hack ni kr liya 🙈🙈🙈
😅😅
For what type of safety we took the size of bool as n+1? why not n?
its a kind of thinking that if you have some extra space for some edge cases that will be helpful ... still its not always necessary you can most of the time use only 'n' but as a built habit we used generally n+1
i tried this with java and there were so many unknown errors and exceptions coming out !! do u suggestt me to do atleast graphs with cpp ?
Yes bro,in java i written correct code only but it give wrong I dry run more than 5 time the code is correct only bro
Very nice video, bhaiya
Thanks a lot
please keep sharing my videos or channel in your colleges or groups please
explanation is good Thanks bhaiya next video kab tak ayega
Thora time me I will upload asap
isme edges adjacency list hai kya ???
@@PIYUSH-lz1zq hei to
Bhaiya mein apne se try kiya but thora error rehe gaya
bool validPath(int n, vector& edges, int source, int destination) {
unordered_map umap;
for (auto x : edges){
vector temp = x;
int u = temp[0];
int v = temp[1];
umap[u].push_back(v);
umap[v].push_back(u);
}
vector vis(n, false);
queue q;
vis[source] = true;
q.push(source);
while (!q.empty()){
int node = q.front();
q.pop();
for (auto x : umap){
vector temp1 = x.second;
for (auto z : temp1){
if (vis[z] == false){
vis[z] = true;
q.push(z);
}
}
}
}
return vis[destination];
}
what if we can do discontinious graph type and if count is one we can return true or else we can return false corect me if iam wrong
MORE CONCISE SOLUTION
bool validPath(int n, vector& edges, int src, int dest) {
if(src == dest) return true;
vector vis(n, 0);
unordered_map adj;
for(auto &it : edges) {
adj[it[0]].push_back(it[1]);
adj[it[1]].push_back(it[0]);
}
queue q;
q.push(src);
vis[src] = 1;
while(!q.empty()) {
int node = q.front();
q.pop();
for(auto &it : adj[node]) {
if(it == dest) return true;
if(!vis[it]) {
vis[it] = 1;
q.push(it);
}
}
}
return false;
}
That's Amazing dost
Thanks a lot
class Solution {
public:
bool validPath(int n, vector& edges, int source, int destination) {
vector adj(n+1);
for(auto i: edges){
adj[i[0]].push_back(i[1]);
adj[i[1]].push_back(i[0]);
}
vector visited(n+1,false);
queue q;
q.push(source);
visited[source]=true;
while(!q.empty()){
int p= q.front();
if(p==destination){
return 1;
} q.pop();
for(auto i: adj[p]){
if(visited[i]==false){
q.push(i);
visited[i]==true;
}
}
}
return false;
}
};
why TLE help plz
arey yaar thanks gottit bhiyya i wrote visted[i]==true; by mistake
bhaiya umap ia unordered map then why u have used push back with umap(it supposed to be insert right ?)??? Please tell me.
yess where i have used that ? it should be insert
Thank You :)
Tried after the knowing logic . Able to code it myself
class Solution {
public:
bool validPath(int n, vector& p, int source, int destination) {
if(destination==source) return true;
unordered_mapm;
for (int i=0;i
amazing brother keep it up
bhaiyaji aap har video main bolte raha karo, ki khud try karo dimag ki nasse khul jati hai try krne main
Hahaha theek hai sure Ashish 😂
Wonderful Series :)
Thanks for supporting Please, share this channel in your college, groups, or LinkedIn bcoz it's cost nothing to you 😀
yes, I have written bfs code 5 times.
Nice 👏
#Python Solution
def validPath(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:
if not edges:
return True
from collections import defaultdict
visited = [False]*(n+1)
count=-1
def _bfs(arr,i):
q = []
q.append(i)
visited[i]=True
while(len(q)>0):
temp = q.pop(0)
for v in arr[temp]:
if not visited[v]:
q.append(v)
visited[v]=True
dic = defaultdict(list)
for a,b in edges:
dic[a].append(b)
dic[b].append(a)
for i in range(len(dic)):
if not visited[i]:
count+=1
_bfs(dic,i)
# print(visited,count)
if visited[destination] and count
great bhaiya😊
🔥🔥
disjoint set can be used to reduce the space complexity
yesss you can but in this playlist our motive is to understand basic of graphs
--------------------------------------------CODE--------------------------------------
class Solution {
public:
bool validPath(int n, vector& edges, int s, int destination) {
vector visited(n+1, false);
//creating adjacency matrix
unordered_map adj;
for(auto edge: edges)
{
adj[edge[0]].push_back(edge[1]);
adj[edge[1]].push_back(edge[0]);
}
queue q;
q.push(s);
visited[s] = true;
while(!q.empty())
{
int u = q.front();
q.pop();
for(auto x: adj[u])
{
if(visited[x] == false)
{
q.push(x);
visited[x] = true;
}
}
}
return visited[destination];
}
};
I have a simple doubt, what if adjaceny of each vertices is greater than 2? What will we do??
than that might be the case of directed graph or that will the adj list only.
if not ,than left to right and make a map ,then traverse right to left again do same thing(you can do both in 1 loop) tc - n^2
My code-class Solution {
public:
bool validPath(int n, vector& edges, int source, int destination) {
unordered_mapadj;
for(int i=0;i
Nice 😊
can we use array inplace of umap like this
bool validPath(int n, vector& edges, int source, int destination) {
vector adj(n + 1);
for (auto x : edges) {
int u = x[0];
int v = x[1];
adj[u].push_back(v);
adj[v].push_back(u);
}
vector visited(n + 1, false);
queue q;
q.push(source);
visited[source] = true;
while (!q.empty()) {
int v = q.front();
q.pop();
for (auto x : adj[v]) { // Traverse the neighbors of the current vertex
if (visited[x] == false) {
visited[x] = true;
q.push(x);
}
}
}
return visited[destination];
}
what if graph is like?
[[0,1],[0,2],[3,1,2],[0]
how to handle this case?
[ [0,1], [0,2], [3,1,2], [0] ]
let adj = []
for(let i=0;i
var validPath = function(n, edges, source, destination) {
if(edges.length == 0){
return true
}
let adj = []
for(let i=0;i
Bhai aapke bolne pr try kiya or ho gya but runtime 587 aa gya🥲
getting memeory limit exceeded error
Hello bhai I am new programing feld
ab to kar liye hoge🤣🤣
Why cant we use recursive DFS ?
you can use ... but my intent to teach the basics of DSA
Bana liya Maharaj😅
Hahahhah
thanks sir😘
welcome sagar
//why it is not working?
class Solution {
public:
bool validPath(int n, vector& edges, int source, int destination) {
for(int i=0;i
6/32 done (31.10.22)
Nice consistency
i am seeing you from last some days
keep learning
@@HelloWorldbyprince thanks bhaiya
maza aa gaya
Keep learning
Please, share this channel in your college, groups, or LinkedIn bcoz it's cost nothing to you 😀
👌👌👌
🥰🥰
agge bhad rahe hai
That's great buddy
Bhai Done
Sir java me bhi code bta dejiye
i will try bro
noice
Thanks ☺️☺️
kardya playlist share
Thanks 👍
Jab padhate ho to confidence nhi dikhta hai... 👎👎👎
🥲
👎
🥲
class Solution {
public:
bool validPath(int n, vector& edges, int source, int destination) {
unordered_map ump;
for (auto x : edges) {
int u = x[0];
int v = x[1];
ump[u].push_back(v);
ump[v].push_back(u);
}
vector visited(n, false);
queue q;
q.push(source);
visited[source] = true;
while (!q.empty()) {
int res = q.front();
q.pop();
for(int x:ump[res]){
if (visited[x] == false) {
q.push(x);
visited[x] = true;
}
}
if (visited[destination])
return visited[destination];
}
return visited[destination];
}
};
vai maine e code kya iska time or space memory bhi bohot kam hua tha.please vai batana mera code thik hai kya nahi
Haan thats not an issue
Agar koi chiz kam lag rha hai
And code run kar gya tha na ?
let adj = []
for(let i=0;i
class Solution {
public:
bool validPath(int n, vector& edges, int source, int destination) {
vectoradjList(n);
for(auto x:edges){
adjList[x[0]].push_back(x[1]);
adjList[x[1]].push_back(x[0]);
}
vectorvisited(n,false);
queueq;
q.push(source);
visited[source]=true;
while(!q.empty()){
int u=q.front();
q.pop();
for(int v:adjList[u]){
if(visited[v]==false){
visited[v]=true;
q.push(v);
}
}
}
return visited[destination];
}
};