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
BELOW IS THE CODE USING SINGLE VISITED ARRAY (VALUE=1 FOR VISITED & VALUE=2 FOR PATHVISITED) . . . . . class Solution { public: bool detectCycleDFS(int node, vector &visited, vector adj[]) { // Put node into Answer visited[node] = 1; visited[node] = 2; // pathVisited // Run DFS on all it's non-visited neighbours for(auto neigh:adj[node]) { if(!visited[neigh]) { if(detectCycleDFS(neigh, visited, adj)) return true; // If any one of the DFS calls returns a True, we keep on returning True } else if(visited[neigh] == 2) { // If a node is visited again on same path, cycle is detected (visited node is also pathVisited) return true; } } // On coming back, omit the node from pathVisited as path is gonna be different now visited[node] = 1; return false; } bool isCyclic(int V, vector adj[]) { vector visited(V, 0); // Behaves as both visited (value = 1) & pathVisited (value = 2) for(int i=0; i
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 am glad that I am able to develop the logic and it has been possible after watching your lectures. Thanks a lot Striver. Solution without using path array: private: bool dfs(vector adj[],vector&vis,int node){ vis[node]=1; for(int it:adj[node]){ if(vis[it]==0){ if(dfs(adj,vis,it))return true; } else{ if(vis[it] == 1)return true; } // cout
Your code is far far from optimal, infact its a brute-force solution. It's computing the same thing over and over again. Here's a correct solution in just a single visited array- 2 means the node is in the current path Once we are returning after exploring a given path, we change visited[currNode] from 2 to 1 Which means the current node is not in the current path anymore, however, it has been visited and does not have a cycle either ``` class Solution { private: bool hasCycle(int currNode, vector adj[], int visited[]){ visited[currNode] = 2; for(int nextNode : adj[currNode]){ if(!visited[nextNode]){ if(hasCycle(nextNode, adj, visited)) return true; } else if(visited[nextNode] == 2){ return true; } } visited[currNode] = 1; return false; } public: bool isCyclic(int V, vector adj[]) { int visited[V] = {0}; for(int node = 0; node < V; node++){ if(!visited[node] && hasCycle(node, adj, visited)) return true; } return false; } }; ```
Thank you soo much bhayya.. for your wondefull explaination using the single visited array bool dfs(int node,vector adj[],vector visited) { visited[node]++; ..marking as visited visited[node]++; //marking its path by increment for(auto i: adj[node]) { if (visited[i] == 0) { if(dfs(i, adj, visited)) return true; } else if (visited[node] == 2) return true; } visited[node]--; //unpathing return false; } bool isCyclic(vector& edges, int v, int e) { // Write your code here vector adj[v]; //creating adj list for(auto edge: edges) { int from = edge[0]; int to = edge[1]; adj[from].push_back(to); } vector visited(v,0); // vector path(v,0); for(int i=0;i
The moment i heard path, I stopped the video and coded the solution and it passed. Thanks to recursion playlist (subsequence pattern). DFS + subsequence. Understood!!! Code Reference: public boolean isCyclic(int V, ArrayList adj) { Set vis = new HashSet(); for(int i=0; i
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
Striver has taught us backtracking so well, this is question is a cake walk for us.😂
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.
Understood! Super awesome explanation as always, thank you very much!!
Using single array was new to me .... Thanks a lot man 🙏🏻❤
Understood!
Super awesome explanation
Great solution and explanation. Reminds me of print all subsubsequence problem.
without watching understood! ❤️ cause everyone knows why..
ban gya cool?
rating kitni hai
Thank You So Much for this wonderful video...........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
Thanks bro for ur awesome work....BTW 16:41😋
Very helpful video, thank you so much bhaiya!!
Backtracking explanation is fantastic
understood striver
as always easy and great explanation
this series is too good!
Next level explanation!💥
Understood!!! awesome as usual
the idea of using just 1 array is amazing
These videos are incredible
Understood. Really wonderful lecture series.
Thanks man for the wonderful explanation, Grateful!
it is an easy problem, just we have to get the logic of that we are in the same path, thank you STRIVER
This is an excellent explanation.
Understood!! Thanks a lot Striver
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
He is the OG
brilliantly explained
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
Loved this video🎉
You are amazing, keep doing these
Great explanation!!
Thank you, Striver 🙂
Understood!
Wow 🤯
understood striver bhaiyaaaaa.................
mast video hai bhai 👌👌
op intuition and amazing concept!! tysm
Great explaination 👍
blown away, understood
I completed the homework u gave in a min
Thank u soo much for making it soo easyy!!!!
U r a legend!!!
understood very nicely sir great explaination 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...
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
Understood, thank you so much.
Really ,youre taking us f/w..❤
// 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
UNDERSTOOD;
Understood! thank you very much!!
Great explaination
You are a legend
understoood
understood! thanks a lot sir!
BELOW IS THE CODE USING SINGLE VISITED ARRAY (VALUE=1 FOR VISITED & VALUE=2 FOR PATHVISITED)
.
.
.
.
.
class Solution {
public:
bool detectCycleDFS(int node, vector &visited, vector adj[]) {
// Put node into Answer
visited[node] = 1;
visited[node] = 2; // pathVisited
// Run DFS on all it's non-visited neighbours
for(auto neigh:adj[node]) {
if(!visited[neigh]) {
if(detectCycleDFS(neigh, visited, adj)) return true; // If any one of the DFS calls returns a True, we keep on returning True
} else if(visited[neigh] == 2) { // If a node is visited again on same path, cycle is detected (visited node is also pathVisited)
return true;
}
}
// On coming back, omit the node from pathVisited as path is gonna be different now
visited[node] = 1;
return false;
}
bool isCyclic(int V, vector adj[]) {
vector visited(V, 0); // Behaves as both visited (value = 1) & pathVisited (value = 2)
for(int i=0; i
bro just use visited[node] = 2; no need for the statement above it
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 am glad that I am able to develop the logic and it has been possible after watching your lectures. Thanks a lot Striver.
Solution without using path array:
private:
bool dfs(vector adj[],vector&vis,int node){
vis[node]=1;
for(int it:adj[node]){
if(vis[it]==0){
if(dfs(adj,vis,it))return true;
}
else{
if(vis[it] == 1)return true;
}
// cout
Your code is far far from optimal, infact its a brute-force solution. It's computing the same thing over and over again.
Here's a correct solution in just a single visited array-
2 means the node is in the current path
Once we are returning after exploring a given path, we change visited[currNode] from 2 to 1
Which means the current node is not in the current path anymore, however, it has been visited and does not have a cycle either
```
class Solution {
private:
bool hasCycle(int currNode, vector adj[], int visited[]){
visited[currNode] = 2;
for(int nextNode : adj[currNode]){
if(!visited[nextNode]){
if(hasCycle(nextNode, adj, visited)) return true;
}
else if(visited[nextNode] == 2){
return true;
}
}
visited[currNode] = 1;
return false;
}
public:
bool isCyclic(int V, vector adj[]) {
int visited[V] = {0};
for(int node = 0; node < V; node++){
if(!visited[node] && hasCycle(node, adj, visited)) return true;
}
return false;
}
};
```
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;
}
thank you Striver
Thank you Legend
Understood 💯💯💯
thanks striver🙌
guruji tussi grt ho
Thank you sir
4:32 - in the same recursive stack
Thank you soo much bhayya.. for your wondefull explaination
using the single visited array
bool dfs(int node,vector adj[],vector visited)
{
visited[node]++; ..marking as visited
visited[node]++; //marking its path by increment
for(auto i: adj[node])
{
if (visited[i] == 0) {
if(dfs(i, adj, visited))
return true;
}
else if (visited[node] == 2)
return true;
}
visited[node]--; //unpathing
return false;
}
bool isCyclic(vector& edges, int v, int e)
{
// Write your code here
vector adj[v];
//creating adj list
for(auto edge: edges)
{
int from = edge[0];
int to = edge[1];
adj[from].push_back(to);
}
vector visited(v,0);
// vector path(v,0);
for(int i=0;i
for(auto i: adj[node])
{
if (visited[i] == 0) {
if(dfs(i, adj, visited))
return true;
}
else if (visited[I] == 2)
return true;
}
*CORRECT CODE*
Understood, Thanks
Thanks for the helpful tutorial! :)
understood, thank you!
great crisp xplntion
Just understood 😀
Thank you !!
☺☺☺☺☺
Understood 😊
Just Awesome
we could have also created new boolean[V] for pathVis[] for each vertex instead of working with single array to save memory
I don't know if it's just me but Your keystrokes sounds funny🙃
Understood❤
Great❤
thank you so much and also understood
Thank you!
understood😊
Understood 🤠
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
space complexity of 2 boolean array < 1 int/short array
great intitution
Maza aa gya vai
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
Understood sir
Thank you bhaiya
understood thank you
The moment i heard path, I stopped the video and coded the solution and it passed. Thanks to recursion playlist (subsequence pattern). DFS + subsequence.
Understood!!!
Code Reference:
public boolean isCyclic(int V, ArrayList adj) {
Set vis = new HashSet();
for(int i=0; i
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
Best in the game aur isme do rai nahi !!
instead of using path visited array we can use backtracking approach also
so we just analyse the recurrsion stack if we visited that node again or not superb algorithm
good one
Understood !!