Please add more videos in the graph series part2 of other algorithms
what lecture you think I should add in that series ?
good job broā¦you helped many of d begginers with the frigthening topicsā¦this has helped me a lotā¦jazakumallah khair
thank you
mistake in else if loop of dfs function else if(color[src]==color[x]), this one comes in place of your condition
First of all , i think you didnāt see there are two testcases. So for first test case n=3 , m=3 and for second test case n=4 m=2.
Brother both are same either i will use color[src] or c , because i pass c by call by call it means everytime a new copy is geneated, So i m sure that it is correct , I think there is an fault in another line
nice1
You are live motivation bro !!! thanks a lot for all your efforts
Can someone tell me if these lectures are useful for INOI ?
Need Help to find the mistake
I am getting WA.
I looked at your solution.
but canāt find the mistake.
import java.util.;
import java.lang.;
class Main
{
public static void main (String[] args) throws java.lang.Exception
{
Scanner sc=new Scanner(System.in);
int test=sc.nextInt();
for(int t=1;t<=test;t++)
{
int n=sc.nextInt();
int m=sc.nextInt();
int visited[]=new int[n+1];
int color[]=new int[n+1];
Map<Integer,List<Integer>> al=new HashMap<>();
for(int i=1;i<=n;i++)
al.put(i,new ArrayList<Integer>());
for(int i=0;i<m;i++)
{
int u=sc.nextInt();
int v=sc.nextInt();
al.get(u).add(v);
al.get(v).add(u);
}
boolean ans=true;
for(int i=1;i<=n;i++)
{
if(visited[i]==0)
{
boolean ca=check(i,0,al,visited,color);
if(ca==false)
ans=false;
}
}
System.out.println("Scenario #"+t+":");
if(ans==false)
{
System.out.println("Suspicious bugs found!");
}
else
{
System.out.println("No suspicious bugs found!");
}
}
}
public static boolean check(int v,int c,Map<Integer,List<Integer>> al,int visited[],int color[])
{
visited[v]=1;
color[v]=c;
//System.out.println("trace "+v+" "+color[v]);
for(int node:al.get(v))
{
if(visited[node]==0)
{
c=c^1;
boolean ans=check(node,c,al,visited,color);
if(ans==false)
return false;
}
else
{
// System.out.println("tr "+v+" "+color[v]+" "+node+" "+color[node]);
if(color[v]==color[node])
return false;
}
}
return true;
}
}
In the counting rooms problem on CSES, I have used the same algorithm used in video but I am still getting TLE on test cases 9 and 10. What is happening? Iām using python 3. Did anyoneās python solution get accepted?
Code is here.
which problem are you solving?
in dfs function you are passing visited array and I am not sure if in python function calls are by reference or by value.
if python follows call by value then you need to stop passing visited array and define it globally
i am trying to solve this problem.
here is my solution: Solutions/Bug_Life.java at master Ā· jarvis-007/Solutions Ā· GitHub
By the way i completed the graph theory playlist today. It was really awesome.
Thank you very much. Eagerly waiting for more videos.
your code is perfectly fine except at one point where you are messing with color.
in dfs function when you are making recursive calls to child of certain node ,
if parent has color c then all itās children must get color c^1.
what you are doing is changing the value of color by setting c = c^1.
this should not happen.
suppose current node say node 1 has 3 children(2 , 3 and 4) nodes and c for node 1 is 0.
so all child of node 1 should get color 1.
suppose you are making call to node 2 then node 3 then node 4.
when you are making call to node 2 you are updating c to 1 from 0 and making call to 2.
so this is good
but now when you have to make call to 3 you are again updating c , this time it will become 0 so 3 will get color 0 which is not good.
so do not update c again and again , just pass the value c^1 in dfs function.
in simple words , instead of this
if(visited[node]==0)
{
c=c^1;
boolean ans=check(node,c,al,visited,color);
if(ans==false)
return false;
}
do this
if(visited[node]==0)
{
boolean ans=check(node,c^1,al,visited,color);
if(ans==false)
return false;
}
.
it was a silly mistake.
Thank you for pointing that out.
i am waiting for further videos on graph theory.
I did it globally and now itās TLE in one more test case (no. 8) too. Itās not reference by value by the way. Is there any other method thatās faster than this?