Let's continue the habit of commenting “understood” if you got the entire video. Please give it a like too, you don't 😞 Do follow me on Instagram: striver_79
I cant do anything to support u.... So , showing my love and support by commenting... Hats off to all ur efforts and thanq for everything ,you are doing for the community ❣
It is now became a habit of just watch explanation and code by yourself. 😊😊 Thank you Striver ,Never thought that i can be able to solve graph problem by my own in just one go
Using single visited array : /*Complete the function below*/ class Solution { // Function to detect cycle in a directed graph. public static boolean dfs(int src, int[] visited, ArrayList adj) { //Mark the node as visited visited[src] = 2;
public boolean dfsTechnique2(int V, ArrayList adj) { // code here int[] vis = new int[V]; for (int i = 0; i < V; i++) { if (vis[i] == 0) { if (dfs2(i, adj, vis)) { return true; } } } return false; } public boolean dfs2(int node, ArrayList adj, int[] vis) { vis[node] = 2; ArrayList neigh = adj.get(node); for (int i : neigh) { if (vis[i] == 0) { if (dfs2(i, adj, vis)) { return true; } } else { if (vis[i] == 2) { return true; } } } vis[node] = 1; return false; } This is my space otpimized code, giving me TLE in case 201.
I am glad that we have Striver❣he's real gem I expected ki mera Bf inti achi DSA padhata muje khud to amazon chla gaya Kash Striver mera bf hota ,but it okay ,i have Striver on utube , i am learning and growing
Can we find the Cycle using BFs ?? In BFs we are not exploring in single path unlike in DFs, I think in BFs we cannot determine that we encountered the node in same path or not. Correct me if I am wrong
Striver bhaiya kindly fix the numbering for this particular video as it is showing at last instead of the order that this particular video has to be in..🙂🙂🙂🙃🙃
homework for only vis arr , we can take cnt as2 each time we visit(as it signifies vis +path) and while returning we could set it to 1 and if vis[node]&&vis[node]==2 return true;
I tried to output cycle path using path rray which you using , in case of 4 vertex and edge as below 1 2 2 3 3 4 4 2 Path array will give 1 2 3 4 but actual answer will be 2 3 4 only am i right ?
Understood... but you already have this topic covered in your Graph series... will that video be replaced by this..? Or is it a beginning of a new series altogether...?
Let's continue the habit of commenting “understood” if you got the entire video. Please give it a like too, you don't 😞
Do follow me on Instagram: striver_79
when i used pathVis array instead of vis arr in "traverse for adjacent nodes" section {Line -15} . I am getting TLE, could anyone explain me why?
@@adityasinghjadon5760 path[I] came back to zero when cycle not in that path,so the node never consider as visited ,time limit exceed
yes
I cant do anything to support u....
So , showing my love and support by commenting...
Hats off to all ur efforts and thanq for everything ,you are doing for the community ❣
did you took TUF+ subscription ? like u wrote "can anything for striver"
The concept of visited and path visited is really amazing
Facts. This concept seems to stick with me the most
Visited pathVisited rocks
understood !!!
only youtuber who made coding easy for us.
Rest others are busy in making cringe video of 3 lpa to 1 cr lpa types video.
It is now became a habit of just watch explanation and code by yourself. 😊😊
Thank you Striver ,Never thought that i can be able to solve graph problem by my own in just one go
private boolean DFS(int i,int[] vis,ArrayList adj){
vis[i]=1;
for(int it:adj.get(i)){
if(vis[it]==0){
if(DFS(it,vis,adj)){
return true;
}
}
else if(vis[it]==1){
return true;
}
}
vis[i]=2;
return false;
}
without the pathVis approach.
Great leacture.
Can you please tell why we always declare the other function as private?
@@saimasyeda6544 Doesn't Matter here, Its just one of OOPS Concept
@@aniketainapur3315 OK thanks
Understood well and doing dry run on my own got the algo into my head. Truly amazing brother💯.
Best explanation and logic abstraction ever!!! Thanks a lot
Understood! Super awesome explanation as always, thank you very much!!
Using single array was new to me .... Thanks a lot man 🙏🏻❤
Using single visited array :
/*Complete the function below*/
class Solution {
// Function to detect cycle in a directed graph.
public static boolean dfs(int src, int[] visited, ArrayList adj)
{
//Mark the node as visited
visited[src] = 2;
for(int nbr : adj.get(src))
{
//If unvisited
if(visited[nbr] == 0)
{
//Mark it as same path
visited[nbr] = 2;
if(dfs(nbr,visited,adj) == true)
{
return true;
}
}
else if(visited[nbr] == 2)
{
return true;
}
}
//Backtrack to visited
visited[src] = 1;
return false;
}
public boolean isCyclic(int V, ArrayList adj) {
// code here
//Space optimization using only visited array
int[] visited = new int[V];
Arrays.fill(visited, 0);
/*
0 - Unvisited
1 - Visited
2 - Same Path
*/
for(int i = 0 ; i < V ; i++)
{
if(visited[i] == 0)
{
if(dfs(i,visited,adj) == true)
{
return true;
}
}
}
return false;
}
}
visited[nbr] = 2; this statement in line number 12 is not necessary right, because however in dfs call you will be marking it as 2
@@santoshb7776 Yes
@@santoshb7776 Yeah
public boolean dfsTechnique2(int V, ArrayList adj) {
// code here
int[] vis = new int[V];
for (int i = 0; i < V; i++) {
if (vis[i] == 0) {
if (dfs2(i, adj, vis)) {
return true;
}
}
}
return false;
}
public boolean dfs2(int node, ArrayList adj, int[] vis) {
vis[node] = 2;
ArrayList neigh = adj.get(node);
for (int i : neigh) {
if (vis[i] == 0) {
if (dfs2(i, adj, vis)) {
return true;
}
}
else {
if (vis[i] == 2) {
return true;
}
}
}
vis[node] = 1;
return false;
}
This is my space otpimized code, giving me TLE in case 201.
Shuru majboori mai kiya tha pr ab maja aane laga hai🙂🙃😊!!!
Striver has taught us backtracking so well, this is question is a cake walk for us.😂
10/10 lecture. Very useful
Understood!
Super awesome explanation
Thanks bro for ur awesome work....BTW 16:41😋
Great solution and explanation. Reminds me of print all subsubsequence problem.
Thank You So Much for this wonderful video...........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
Very helpful video, thank you so much bhaiya!!
without watching understood! ❤️ cause everyone knows why..
ban gya cool?
rating kitni hai
Thanks man for the wonderful explanation, Grateful!
Understood!!! awesome as usual
Next level explanation!💥
this series is too good!
Understood!! Thanks a lot Striver
These videos are incredible
understood striver
as always easy and great explanation
Understood. Really wonderful lecture series.
Backtracking explanation is fantastic
This is an excellent explanation.
Loved this video🎉
You are amazing, keep doing these
I am glad that we have Striver❣he's real gem
I expected ki mera Bf inti achi DSA padhata muje khud to amazon chla gaya
Kash Striver mera bf hota ,but it okay ,i have Striver on utube , i am learning and growing
brilliantly explained
Great explanation!!
op intuition and amazing concept!! tysm
it is an easy problem, just we have to get the logic of that we are in the same path, thank you STRIVER
Thank you, Striver 🙂
// single visited array code:
class Solution {
public:
bool dfs(int s, vector &visited, vector adj[]) {
visited[s] += 1;
visited[s] += 1;
for(int ele: adj[s]) {
if(visited[ele] == 0) {
if(dfs(ele, visited, adj) == true) return true;
}
else if(visited[ele] == 2) {
return true;
}
}
visited[s] -= 1;;
return false;
}
// Function to detect cycle in a directed graph.
bool isCyclic(int V, vector adj[]) {
vector visited(V, 0);
for(int i=0;i
16:28
bool dfs(int node, vector adj[], int vis[]){
vis[node]=2;
for(auto it:adj[node]){
if(!vis[it]){
if(dfs(it, adj, vis)==true)
return true;
}
else if(vis[it]==2)
return true;
}
vis[node]=1;
return false;
}
//main function remains the same
Great explaination 👍
C++ code using a single Visited array : bool dfs(vector adj[],vector&visited,int start){
visited[start] = 1;
int temp = visited[start];
visited[start] = 2;
for(auto &neighbour : adj[start]){
if(visited[neighbour]==0){
if(dfs(adj,visited,neighbour)==true) return true;
}
else if(visited[neighbour] == 2){
return true;
}
}
visited[start] = temp;
return false;
}
bool isCyclic(int V, vector adj[]) {
vectorvisited(V,0);
for(int i=0;i
Really ,youre taking us f/w..❤
Understood!
Wow 🤯
Can we find the Cycle using BFs ?? In BFs we are not exploring in single path unlike in DFs, I think in BFs we cannot determine that we encountered the node in same path or not. Correct me if I am wrong
We will have an algorithms for bfs as well in coming lectures
He is the OG
blown away, understood
understood very nicely sir great explaination sir
mast video hai bhai 👌👌
Understood, thank you so much.
understood striver bhaiyaaaaa.................
Using single vis array :
class Solution {
private:
bool dfs(int node,vector adj[], vector&vis){
vis[node]=2;
for(auto it : adj[node]){
if(!vis[it]){
if(dfs(it,adj,vis)){
return true;
}
}
else if(vis[it]==2){
return true;
}
}
vis[node]=1;
return false;
}
public:
// Function to detect cycle in a directed graph.
bool isCyclic(int V, vector adj[]) {
// code here
vectorvis(V,0);
for(int i =0 ; i
nice one
isnt it same because any way you are using int data type for marking vis array which is already taking double space in comparison to bool data type?
@@fivexx469 Yeah its same
I completed the homework u gave in a min
Thank u soo much for making it soo easyy!!!!
U r a legend!!!
understood! thanks a lot sir!
Haven't seen the video yet but will definitely edit this comment to 'understood' after watching it. :) Thanks Striver Bhaiiyyaaaaaaaaaa
i think you forgot ? go huuryy and edit this
Hello bro... Waiting for your "Understood".
Still wiating
bhai dekh le video, placement season aa raha hai
Bhai ab to samajh jaa...
the idea of using just 1 array is amazing
instead of using path visited array we can use backtracking approach also
Understood! thank you very much!!
Understood 💯💯💯
great crisp xplntion
Thanks for the helpful tutorial! :)
Great explaination
Code using only single visited array:
class Solution {
bool util(vector adj[],int u,vector &vis){
vis[u] = 1;
for(auto v:adj[u]){
if(vis[v] == -1){
if(util(adj,v,vis))
return true;
}else if(vis[v] == 1)
return true;
}
vis[u] = 0;
return false;
}
public:
// Function to detect cycle in a directed graph.
bool isCyclic(int V, vector adj[]) {
// code here
vector vis(V,-1);
for(int i=0;i
You are a legend
thanks striver🙌
thank you Striver
understoood
understood, thank you!
Striver bhaiya kindly fix the numbering for this particular video as it is showing at last instead of the order that this particular video has to be in..🙂🙂🙂🙃🙃
Why is pathVis[i] set to 0 before exiting function? We are not passing pathVis by reference anyways. It will take the old state only.
pathVis[] is an array not vector. Aarays are pass by reference
Thank you Legend
homework
for only vis arr , we can take cnt as2 each time we visit(as it signifies vis +path) and while returning we could set it to 1 and if vis[node]&&vis[node]==2 return true;
Just understood 😀
UNDERSTOOD;
Thank you sir
Understood, Thanks
why aren't we passing vis and pathVis by reference?I think after going back to prev function, we will loss data of vis
great intitution
I tried to output cycle path using path rray which you using ,
in case of 4 vertex and edge as below
1 2
2 3
3 4
4 2
Path array will give 1 2 3 4 but actual answer will be 2 3 4 only
am i right ?
Solution:
class Solution {
private:
bool dfsCheck(int node, vector adj[], int visited[]){
visited[node] = 2;
for(auto it: adj[node]){
if(visited[it] == 0){
if(dfsCheck(it,adj,visited) == true){
return true;
}
}
else if(visited[it] == 2){
return true;
}
}
visited[node] = 1;
return false;
}
public:
// Function to detect cycle in a directed graph.
bool isCyclic(int V, vector adj[]) {
// code here
int visited[V] = {0};
for(int i = 0;i < V;i++){
if(visited[i] == 0){
if(dfsCheck(i,adj,visited) == true){
return true;
}
}
}
return false;
}
};
Thank you !!
☺☺☺☺☺
guruji tussi grt ho
thank you so much and also understood
Using one visited array
bool dfs(int node, int vis[], vector adj[]) {
vis[node] = 2;
// visit adjacent nodes
for(auto adjacentNode: adj[node]) {
// unvisited adjacent node
if(!vis[adjacentNode]) {
if(dfs(adjacentNode,vis,adj))
{
return true;
}
}
else if(vis[adjacentNode]==2) return true;
}
vis[node]=1;
return false;
}
4:32 - in the same recursive stack
I don't know if it's just me but Your keystrokes sounds funny🙃
You should have made videos by doing some codes in c and some codes in java. That would be able to cater to both java and c students
Understood❤
Understood 😊
Hey Striver, I have a request. Can you please put the java code in white bg? Its a little difficult to comprehend with the dark bg. Thank you!
Sure, thanks will do it from the upcoming videos.
Just Awesome
we could have also created new boolean[V] for pathVis[] for each vertex instead of working with single array to save memory
understood😊
Understood...
but you already have this topic covered in your Graph series...
will that video be replaced by this..?
Or is it a beginning of a new series altogether...?
Community post refer
good one
Great❤
Why does it fail on Testcase 201, using java , using DFS. BFS passes all the testcases
understood thank you
Thank you!
Hey java peeps, does this code gives a TLE on test case 201 / 410 ?