Thanks for this series @Waqar_ahmad224 I am watching your graph videos. You put in a lot of hard work. Thanks again. I will finish the series and post review.
Thanks man for your work , I can very confidently say that to a larger extent I have learnt CP from your videos
How will we print the shortest path in bfs in graph/2D?
Can some one please post good set of beginner level problems in graph theory.
You can try on hackerearth. They have amazing problems for beginners.
Link - Depth First Search Practice Problems | Algorithms | page 1 | HackerEarth
Bro keep up the GREAT work…I love your videos on graphs…please finish videos on graph theory and start updating on otherslike dp on graphs or trees,and discuss a lot of problems too
-Thanks a lot
thank you
https://www.spoj.com/problems/QUEEN/
Can You please explain this problem ( bfs on 2d grid ) .
Thank you
hey can you make a video on multisource bfs and question rotten oranges from geeksforgeeks
Thanks for your effort man.
The feasible relation(Hackerearth) problem using dfs is not giving ac it gives tle for last two cases.
And using dsu it is also giving tle for the last testcase.
Can you suggest what i am doing wrong
Here is my code :VTwoc2 - Online C++0x Compiler & Debugging Tool - Ideone.com
I added fast I/O in your solution and it gave full marks
In the Editorial too they have used Fast I/O.
Link: M9BWo4 - Online C++0x Compiler & Debugging Tool - Ideone.com
bhai i know applying queue for this algo will be working like a charm , but is it really necessary to use queue , i mean if we have certain nodes which have o internal nodes than it doesnt really depends in which order they are placed , or if i m wrong could u enlighten me , btw thanks for this great lecture.
Can anyone here please tell me how to go about a problem if the numbe of nodes are N but nodes are not as 1,2,3,…N. that is the nodes can be any number and not actually from 1 to N.
Please help anyone!
#include<bits/stdc++.h>
using namespace std;
const int MX=1e2;
vector ar[MX+1];
vector vis(MX+1,0);
vector low(MX+1,0);
vector in(MX+1,0);
set s;
int timer=0;
int children;
void IS_CUTPOINT(int v){
s.insert(v);
}
void dfs(int node,int par=-1){
vis[node]=1;
in[node]=low[node]=timer++;
children=0;
for(int i=0;i<ar[node].size();i++){
int child=ar[node][i];
if(child==par){
continue;
}
if(vis[child]){
low[node]=min(low[node],in[child]);
}
else{
dfs(child,node);
low[node]=min(low[node],low[child]);
if(low[child]>=in[node] && par!=-1){
IS_CUTPOINT(node);
}
++children;
}
}
if(par==1 && children>1){
IS_CUTPOINT(node);
}
}
int main(){
int n,m;
cin>>n>>m;
while(m--){
int a,b;
cin>>a>>b;
ar[a].push_back(b);
ar[b].push_back(a);
}
for(int i=1;i<=n;i++){
if(!vis[i]){
dfs(i);
}
}
cout<<"Articulation points:\n";
for(set<int>::iterator it=s.begin();it!=s.end();it++){
cout<<*it<<"\n";
}
//cout<<"children: "<<children<<"\n";
return 0;
}
I was implementing articulation points algorithm but it is not working for root can’t understand why please help!!!
“if(par==1 && children>1){
IS_CUTPOINT(node);
}” -> The issue is here, You are checking if par == 1 but the root of the Graph is Initialized with -1. Therefore you are facing issue while detecting root as a Cut Vertex.
Bro , You explained this problem(Longest palindromic string) in dp series . But here i am getting segmentation fault but passing all the sample test cases please look into the code i am attaching here .
pastebin - This is the code i have written
Please look into this
Thank you
You can read about the issue you are facing here, You are declaring a 2D array of very large size.
LInk
Oh then will bool array work ??
This question easily solved by hashing , Why DP.
u create DP[N][N] , where N is 2*105 which is too large to allocate , also let say it will allocate but still your code take O(N2) times , gives TLE.
@ssrivastava990
Bro can you please explain hashing approach or provide some resource for that .
Thank you