Graph Theory Complete video series : part 1 (9 july2020 - 1 editorial added)

google rolling hash cp algo , codeforces rolling hash , hashing hackerearth.

1 Like

make video on labriynath cses problemset question

Hey,where can i find the question of the contest held by you on graph

//I have got TLE on PPATH - Prime Path. Can you please help me!

#include<bits/stdc++.h>
using namespace std;
#define vi vector
#define pb push_back

vi ara[100001],primes;

int vis[100001],dis[100001];
bool isprime(int n)
{
for(int i=2;i*i<=n;i++)
{
if(n%i==0)
return false;
}
return true;
}
bool isvalid(int a, int b)
{
int c=0;
while(a!=0)
{
if(a%10!=b%10)
c++;
a=a/10;
b=b/10;
}
if(c==1)
return true;
return false;
}
void buildgraph()
{
for(int i=1000; i<=9999; i++)
{
if(isprime(i))
primes.pb(i);

}
for(int i=0;i<primes.size();i++)
{
    for(int j=i+1;j<primes.size();j++)
    {
        if(isvalid(primes[i],primes[j]))
        {
            ara[primes[i]].pb(primes[j]);
            ara[primes[j]].pb(primes[i]);
        }
    }
}

}
void bfs(int n)
{
queue q;
q.push(n);
vis[n]=1;
dis[n]=0;
while(!q.empty())
{
int curr =q.front();
q.pop();
for(int child:ara[curr])
{
if(vis[child]==0)
{
q.push(child);
vis[child]=1;
dis[child]=dis[curr]+1;
}
}
}
}
int main()
{
int t,n,m,i;
cin>>t;
while(t–)
{
for(i=1000; i<=9999; i++)
{
ara[i].clear();
dis[i]=-1;
vis[i]=0;
}
cin>>n>>m;
buildgraph();
bfs(n);
if(dis[m]==-1)
cout<<“Impossible”<<endl;
else
cout<<dis[m]<<endl;
}
}

bro your videos are good ;
i would appreciate if you would have put more code for beginers like me but thanks anyway

Bro, can I practice vjudge problems now?

Hi CodeNCode

This is my 1st msg in this forum. I wrote some yt comments in the past for multiple videos, but in “L15 : Kahn’s Algorithm” video you suggested to post comments or questions over here.

May I know how to comment for any video of any CodeNCode series?

Madhukiran

Hi Waqar / CodeNCode,

I registered into codechef.com only yesterday. It’s a bit confusing.

Suppose I wanna comment or ask u a question on L17 in graph theory part 1. Shoud I’ve to search for your post on L17 in discuss.codechef.com (like this msg of yours to which I’m replying) OR is there a better way?


Could you please comment my question below❓

For the final problem “Chef and Escaping from the Labyrinth”,
and 1st test,
and 2nd row of output has YNYBY
But I got NNYBY
Is YNYBY a typo, or did I wrongly interpret the presence of 1 or row 3 column 1❓

Madhukiran

Hi CodeNCode,

Why don’t you respond to yt comments? Wouldn’t it be more easier for the audience?

Madhukiran

Hi CodeNCode,

@[4:13] – instead of ar[i].clear() and vis[i] = 0 for every node

why can’t we set vis[i] = test# to mark node as visited
and confirm that node is unvisited if vis[i] < test# ?
O(n) time to clear vis[] array can be avoided

and, instead of clearing every adjacency list in O(m) time, why can’t we init ar as
ar = new vector[100001];
at the start of every test?

I mean, whatever is the equivalent of above java new statement

Would the older graph data used by previous test be automatically garbage collected? Does GC exist in C++?

Please comment back so I can learn

Madhukiran

Hi CodeNCode,

U coded as :
A: if (low[child] > in[node]) print "bridge : " + child " + " - " + node
B: low[node] = min(low[node], low[child])

Can be slightly improved as :
A: if (low[child] > in[node]) print "bridge : " + child " + " - " + node
B: else if (low[child] < in[node]) low[node] = min(low[node], low[child])

Reason :
A: child has no path to node’s ancestor, so edge node-child is a bridge
B: child has a path to node’s ancestor, so lower node’s low time to child’s low time, if feasible
C: If node’s in time is same as child’s low time, node’s low time will be <= child’s low time, coz any node’s low time would always be <= it’s in time, and so it can not be further reduced

A B C are mutually exclusive cases. Performance can be improved if we divide the code into A B C parts.

Please comment/correct.

Madhukiran

In Kruskal’s MST, since we might not process all edges, it would be more efficient to use a min PQ (min heap priority queue) instead of sorting the edges

Makes sense?


Please consider this feedback Waqar…

“raised to the power of” is such a tongue twister. I see it was troubling u many times.

Similarly i-th node, n-th node, j-th node, etc

Instead, it will be easy for u if u say :

“2 power 3”, “n power m”, etc. Folks will certainly understand. There is no need to say “2 to the power of 3”, “n to the power of m” too.

And say :

node number i, node number n, node number j, etc

Try to avoid tongue twisters.

Thankyou! :slight_smile:

  • Madhukiran