This link doesn't seem to work now..i was trying and get stuck at the place where say a pair comes where both dislike values presently do not exist in both the sets..then how would i insert them in different sets..i mean in which order??
Please keep adding all the Interview related graph problems like this, snakes and ladder etc. It will really help us a lot!! Thank you for the amazing explanation XD
I think approach 1 won't work out Ex:- [[1,2],[3,4]] Initialized set A and B Suppose we've followed the way that if either of [a,b] are not present in any set I.e A and B then we'll append 'a' in set A and 'b' in set B. Then after computation set's will be A=[1,3] and B=[2,4] Verdict comes to be true Suppose there also exists another input [1,3] then it turn's out to be false. But actually it's possible if sets are like A=[1,4] and B=[2,3]
so the thing is the input is [[1, 2], [3, 4], [1, 3]]. you will have to sort the input first in order for the method to work. [[1, 2], [1, 3], [3, 4]]. after that follow the algorithm1 gives you the following group1 = [1, 4] group2 = [2, 3]
Note: Disjoint set means the two sets won't be having any common element between them and independent set means there won't be any direct edge between the elements of the same set.
The set/map apporach u talked about wont work unless you handle the case where if two numbers encountered have same set , can we place them differently if some pair before them was placed alternatively. Ex. [1,2],[3,4],[5,6],[1,6] here the sets will have (1,4,5) and (2,3,6) as sets. BUt for [1,2],[3,4],[5,6],[3,6] sets are (1,3,5) and (2,4,6) which differs from before as 3,4 was placed differently here. There are 2 possibilties for placement of a pair where no number appeared before.
Nice Explanation, I was learning this concept since from 10 hours but after watching your explanation in one go I had cleared my all doubts and got all the points about the same.
Also can you make a video on cycle detection in directed vs cycle detection in undirected, actually I know the methods to detect the same but little bit confused, means after implementing those methods question coming to my minds is like" why so ?".
Yes, even I had this question, one suggestion might be, putting those terms in another array and doing the procedure again but ik that will give a TLE for sure. Any Suggestions folks?
@@techdose4u Your pinned comment has a broken link. Your first method with two sets simply doesn't work, you should fix your video to not misinform people in the future.
@@techdose4u Consider the case with these dislikes: [[1,3],[2,5],[3,5]] This case it is possible for a bi-partition, but your 2 set algorithm will fail. How do you know which set to put a number in if you haven't previously seen the number? Answer is that you can't know.
I was able to identify, its graph problem and tried normal cycle detection method (which didn't work) but had no idea about bipartite concept and coloring concept, thanks.
i think it will give a better idea. if there is no cycle then we can always bipartite . and if we have any cycle then : -> if we are able to colour the cycle in such a way that no two adjcent vertices have same colour => we can place the same colour into one set and other into other set => bipartite -> if we are not able to colour in the above mentioned manner => we require atleast 3 colours to colour the graph=> (forming more than 3 sets ) => not bipartite
bro, Crystal clear explanation and the way you walk us through the entire problem is intuitive. Thanks a lot for the video. Please cover all the topics in DS and Algo.
Thanks @Techdose for the explanation very well done . And you always motivate me but in this video I have a comment : If you do not have an odd length cycle that does not mean its bi-partite. So, when you say that we can not find all the odd length cycle that is wrong because even when you find all the odd length cycles you are not correctly checking whether the graph is bipartite or not. Example : [[1,2],[1,3],[2,3]] . There is no cycle here but its not bi-partite. Please correct me if I am wrong.
Hey man I have covered nearly all of your graph playlist and they were greatly beneficial to me. By the way, please make video on Ford Fulkerson Algorithm, Vertex Cover and Graph Colouring problem.
Please explain when you traversed the adjancency list what are the conditions to go to next list of adjancency list, to pop from queue, it is a bit confusing.
It is very simple. Starting node is just an assumption. Now we need to find odd length cycles. For that we used 2-color graph Coloring method. Graph Coloring can be used for finding cycle right. If you confusion in traversal of adj list then first try solving cycle finding in a graph.
Man see the Constraints. their already mentioned always ai < bi. so [ (1;2) (5;3) (2;4) (2;3) (4;5)] this test case is not a valid test case because [5 > 3].
It will fail for graph like 3->2->1 , u first call on 1 , 1 will be colored as color[1] =1 , its adj list is empty , then u will call on 2 in main , and u will color [2] = 1 and 1 is in adjacency list of 2 , and its colored 1 so it will say not possible
Maybe that's true. I dint solve using method 1 myself but since I saw someone had solved using it therefore I included that in the video (only for a short time).
Thanks for the video sir Awesome explanation of the concepts But if we try to do in the 2nd method ,what if the graph has no cycle sir? Like for example [[1,3],[1,4],[2,4]] It has no cycle
I don't understand what is wrong with the method I use. I passed 50/ 70 tests but seem to fail at larger cases. I didn't use dfs/ bfs, I just simply sort the input array and loop through each array to color it. I don't know why this logic fails. Can you please explain to me ? public boolean possibleBipartition(int N, int[][] dislikes) { if(dislikes == null || dislikes.length == 0) return true; int[] color = new int[N + 1]; Arrays.sort(dislikes, (a,b) -> (a[0] - b[0])); for(int[] dislike: dislikes){ int people1 = dislike[0]; int people2 = dislike[1]; if(color[people1] == 0){ if(color[people2] == 0) color[people1] = 1; else{ color[people1] = color[people2] == 1? 2: 1; } } if(color[people2] == 0){ color[people2] = color[people1] == 1? 2: 1; } if(color[people2] != 0 && color[people2] == color[people1]){ return false; } } return true; }
sir the solution using 2 maps/sets will not give correct answer for cases where we will have a pair whose not in any group yet...so where we will insert the values of that pair in which set ??
@@techdose4u let two sets be 1,2 and 3,4 now they form even pair ,now consider 1,2 are connected and 3,4as well so again they form even pair edges but in this case it is not bipartite graph
i tried to solve this problem using DFS but i got an error "Stack overflow" , i cant understand what i did wrong there i'm doing almost same like you. I also have a little request , can you please just take few minutes in your next video and explain how to code in leetcode , I've seen you sometimes you declare vectors and variables in the constructors and sometimes you just pass everything in the function as an argument , Can't we declare globally? BTW your videos are great sir, you are doing a great Job
@@techdose4u I just passed the adjacency list and vector as a parameter to my dfs function and it worked. Defining global was a problem I think. Thank you
10 [[4,7],[4,8],[2,8],[8,9],[1,6],[5,8],[1,2],[6,7],[3,10],[8,10],[1,5],[7,10],[1,10],[3,5],[3,6],[1,4],[3,9],[2,3],[1,9],[7,9],[2,7],[6,8],[5,7],[3,4]] can you please explain this test case. i solved it using two sets and they are expecting true for this while my answer is false. upto [5,8] person 1 and person 2 are in same set so when we check for [1,2] it should return false. but why they are expecting true for it?
It's because when you process element [2,8]. This is the resulting sets: S1={4,2,} & S2={7,8}. Similarly, when you reach element [1,6] both 1 and 6 are not present in either set. So you Set would have been S1={4,2,9,1} & S2= {7,8,6}. So when you process element [1,2], it returns false as both the numbers are present in same set i.e, S1. But if at the time of processing [1,6] if 1 is kept in S2 and 6 in S1, the resultant sets would have been S1 ={4,2,9,6} & S2 = {7,8,1}. So on processing [1,2], this would return true as it possible to place them in separate Sets. So using the 1st (Set/Maps) approach solving this question is tricky. Try implementing 2nd approach.
This is the case for even length cycle. You need to find if the graph has odd length cycle. This must be Test case no 39 where most people got stuck 😅 See the PINNED comment.
No but some testcases fail. I done using this way. The problem with this is if both elements are not there in two sets then the problems comes that is in which set we should place which element??
I used the first method ,but when we find something like if we put 5 in v rather than u it will be true, but result false, can you share a code for first approach?
It is just my habit. Better be safe than sorry 😅 Sometimes nodes start from 1 and sometimes from 0 and so most of the times I end up writing N+1 instead of N.
i tried with the first approach but it is falling, code is written his way I guess it should not fail, can you please check public static boolean possibleBipartition(int N, int[][] dislikes) { HashSet set1 = new HashSet(); HashSet set2 = new HashSet(); for(int i=0;i
Solution can be found at github.com/Ankur-Jat/leetcode-maychallenge/blob/master/week4/day28PossibleBiratrite.py I'm maintaining a github repo for leetcode challenges. Please show some love.
Bro! The first approach you taught will not work, did you tried that? Here is my code: static class node { int x; int y; public node(int x, int y) { this.x = x; this.y = y; } } public boolean possibleBipartition(int N, int[][] dislikes) { if (dislikes.length == 0) return false; ArrayList list = new ArrayList(); for (int i = 0; i < dislikes.length; i++) { list.add(new node(dislikes[i][0], dislikes[i][1])); } HashSet set1 = new HashSet(); HashSet set2 = new HashSet(); for (int i = 0; i < list.size(); i++) { if (set1.contains(list.get(i).x)) { if (set1.contains(list.get(i).y)) return false; set2.add(list.get(i).y); } else if (set2.contains(list.get(i).x)) { if (set2.contains(list.get(i).y)) return false; set1.add(list.get(i).y); } else if(set1.contains(list.get(i).y)){ if (set1.contains(list.get(i).x)) return false; set2.add(list.get(i).x); } else if(set2.contains(list.get(i).y)){ if (set2.contains(list.get(i).x)) return false; set1.add(list.get(i).x); } else { set1.add(list.get(i).x); set2.add(list.get(i).y); } System.out.println(set1 +" "+ set2); } return true; }
SOLUTION: Using 2 SETs in PYTHON:leetcode.com/problems/possible-bipartition/discuss/655026/Using-two-sets-with-out-graph
thanks a lot for the solution
Thanks to the coder who shared 2 SET code :)
Please search on leetcode discussions. I am sure you will get it there.
This link doesn't seem to work now..i was trying and get stuck at the place where say a pair comes where both dislike values presently do not exist in both the sets..then how would i insert them in different sets..i mean in which order??
@@darshankhandelwal9072 yeah true, I'm too struck in the same problem
I personally think that you are the king of algorithms and data structure because the person who knows really can explain precisely
Please keep adding all the Interview related graph problems like this, snakes and ladder etc. It will really help us a lot!! Thank you for the amazing explanation XD
Welcome :)
I think approach 1 won't work out
Ex:- [[1,2],[3,4]]
Initialized set A and B
Suppose we've followed the way that
if either of [a,b] are not present in any set I.e A and B then we'll append 'a' in set A and 'b' in set B.
Then after computation set's will be
A=[1,3] and B=[2,4]
Verdict comes to be true
Suppose there also exists another input [1,3] then it turn's out to be false.
But actually it's possible if sets are like A=[1,4] and B=[2,3]
Approach 1 already worked and CODE is given in PINNED comment.
you are right....faced the same difficulty with first approach...
@@techdose4u you have pinned code with coloring method not hashset method...
I guess Manikanta is correct.
so the thing is the input is [[1, 2], [3, 4], [1, 3]]. you will have to sort the input first in order for the method to work.
[[1, 2], [1, 3], [3, 4]]. after that follow the algorithm1 gives you the following
group1 = [1, 4]
group2 = [2, 3]
Brilliantly articulated and explained. All I was looking for was a clear explanation before diving into the code! Keep 'em coming.
Thanks :)
Great explanation. Thanks for covering the "multi-component" case in the graph solution. That was something I was having trouble with yesterday.
Welcome :)
Note: Disjoint set means the two sets won't be having any common element between them and independent set means there won't be any direct edge between the elements of the same set.
Thanks for the Clarification. I was also confused initially.
In-depth, precise and very calm explanation.
The set/map apporach u talked about wont work unless you handle the case where if two numbers encountered have same set , can we place them differently if some pair before them was placed alternatively. Ex. [1,2],[3,4],[5,6],[1,6] here the sets will have (1,4,5) and (2,3,6) as sets. BUt for
[1,2],[3,4],[5,6],[3,6] sets are (1,3,5) and (2,4,6) which differs from before as 3,4 was placed differently here. There are 2 possibilties for placement of a pair where no number appeared before.
Please go through the CODE link given in PINNED comment.
Nice Explanation, I was learning this concept since from 10 hours but after watching your explanation in one go I had cleared my all doubts and got all the points about the same.
Also can you make a video on cycle detection in directed vs cycle detection in undirected, actually I know the methods to detect the same but little bit confused, means after implementing those methods question coming to my minds is like" why so ?".
The method I showed using 3 states can be used for both types of graph.
Why is this the best series i have ever watched?
I am sure you will be having more than 1 million subscribers.
Splendid explanation 👌
Very soon.
Thanks for motivation :)
For your first approach, if you encounter a pair in which both values present in neither set, how to do determine which set to insert which value
Yes, even I had this question, one suggestion might be, putting those terms in another array and doing the procedure again but ik that will give a TLE for sure.
Any Suggestions folks?
I dint solve using this method but some people did. Try to get your doubt cleared from the Pinned comment.
@@techdose4u Your pinned comment has a broken link. Your first method with two sets simply doesn't work, you should fix your video to not misinform people in the future.
@@techdose4u Consider the case with these dislikes: [[1,3],[2,5],[3,5]] This case it is possible for a bi-partition, but your 2 set algorithm will fail. How do you know which set to put a number in if you haven't previously seen the number? Answer is that you can't know.
One thing i would like to add up the graph at 7:34 is undirectional as if a hates b,b also hates a
I was able to identify, its graph problem and tried normal cycle detection method (which didn't work) but had no idea about bipartite concept and coloring concept, thanks.
Welcome :)
Your content is really good. Continue making such video with clear and concise explanation.
Yes I will :)
a lot of concepts covered in a single problem. very well explained :-)
Thanks :)
i think it will give a better idea. if there is no cycle then we can always bipartite . and if we have any cycle then :
-> if we are able to colour the cycle in such a way that no two adjcent vertices have same colour => we can place the same colour into one set and other into other set => bipartite
-> if we are not able to colour in the above mentioned manner => we require atleast 3 colours to colour the graph=> (forming more than 3 sets ) => not bipartite
Always clear cut explanation ♥️
Thanks :)
code for DFS approach..
class Solution {
public:
bool bipartite(int i,vector& colour,vector& adj,int cc)
{
colour[i]=cc;
for(int x:adj[i])
{
if(colour[x]==cc)
return false;
if(colour[x]==-1)
bipartite(x,colour,adj,1-colour[i]);
}
return true;
}
bool possibleBipartition(int N, vector& dislikes) {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n=dislikes.size();
vector adj(N+1);
for(int i=0;i
👍
I was only able to think via 2 map,but another approach great man.
2 map is not the proper approach for this problem. DFS/bfs with Coloring is the process.
Learned a lot from this video
Thank you for such a clear and concise explanation.
Thanks :)
bro,
Crystal clear explanation and the way you walk us through the entire problem is intuitive. Thanks a lot for the video. Please cover all the topics in DS and Algo.
Welcome. Sure bro :)
This channel is boon for Leetcoders!
😅 :P
please make a clear video on Generate all the binary strings of N bits and how the code is working. Please 🙏
Thank you very much for a very clear explanation. I'm still not good solving graph problems
Keep practicing and learning.
Great Explaination!
Thank You!!
Welcome
Thanks for this video. Really helped in understanding the concept.
Welcome :)
It is a very simple problem. This video makes it complex, especially the bipartition graph section. Hate it!
Thanks @Techdose for the explanation very well done . And you always motivate me but in this video I have a comment : If you do not have an odd length cycle that does not mean its bi-partite. So, when you say that we can not find all the odd length cycle that is wrong because even when you find all the odd length cycles you are not correctly checking whether the graph is bipartite or not.
Example : [[1,2],[1,3],[2,3]] .
There is no cycle here but its not bi-partite.
Please correct me if I am wrong.
Best teacher ever!
Thanks
sir please solve using Union Find too.
I will try sometime later :)
Really Great Explanation. Thank You!
Welcome :)
great explaination buddy!!
Thanks
taking a boolean array instead of map and set will improve runtime
Yes.
Gadar gadar gadar🔥🔥🔥
😀
U just nailed it as always .....keep it up👌👌💥
Thanks
B 1.2 CR, S 1.3 CR J 39L
Thank you so much for a detailed explanation
Welcome :)
Why we are declaring 'adj' size and 'color' size as n+1?
Hey man I have covered nearly all of your graph playlist and they were greatly beneficial to me. By the way, please make video on Ford Fulkerson Algorithm, Vertex Cover and Graph Colouring problem.
Nice. Those will be covered in separate course.
@@techdose4u You're one of the best creators of programming videos.
thanks dude, great explanation
Sir Leetcode has announced a June Challenge too. Can you please cover that as well?
Shit!! Have they? I won't get any breather 🤣 I have no choice but to cover 😅
@@techdose4u Sir you saying that you will cover it made my day!!!
Best Explanation on this Topic I got so far 🙌
Thanks
Hello there, Now this is really awesome explanation.
What if (1,3),(3,2) and (4,1) are the inputs? Then the edges are 3(odd) but still, we can split into two groups
You are simply awesome!
😅
Very nice explanation 👌👌
Please explain when you traversed the adjancency list what are the conditions to go to next list of adjancency list, to pop from queue, it is a bit confusing.
It is very simple. Starting node is just an assumption. Now we need to find odd length cycles. For that we used 2-color graph Coloring method. Graph Coloring can be used for finding cycle right. If you confusion in traversal of adj list then first try solving cycle finding in a graph.
best explanation ever!
Thanks :)
What if array were [ (1;2) (5;3) (2;4) (2;3) (4;5)]
In this case your first approach of Hash-Set won't work
You said it man. I was looking for someone who would comment this. :) . You are absolutely correct.
Man see the Constraints. their already mentioned always ai < bi. so [ (1;2) (5;3) (2;4) (2;3) (4;5)] this test case is not a valid test case because [5 > 3].
It will fail for graph like 3->2->1 , u first call on 1 , 1 will be colored as color[1] =1 , its adj list is empty , then u will call on 2 in main , and u will color [2] = 1 and 1 is in adjacency list of 2 , and its colored 1 so it will say not possible
although we can bipartite 3->2->1
No. My aim is to find odd length cycle. Your example 3->2->1 is not a cycle. I am finding negative cases so that rest all cases will be positive.
@@techdose4u ya its not a cycle but code will give it odd cycle
@@techdose4u run code over this directed graph 3->2->1
great explanation !! thanks a lot.
Welcome :)
Thank you so much Surya Sir
Welcome
Is it possible on directed graphs? also how u said O(V+E) as O(V) , infact E is around V^2
V+E is the actual complexity. It ranges from V to V+V^2 depending on graph sparsity.
Nice explanation!
Thanks :)
amazing explanation
Nice Work bro!!!
Thanks
Approach one is wrong. The solution you pinned is now giving WA since leetcode must have added more test cases.
Maybe that's true. I dint solve using method 1 myself but since I saw someone had solved using it therefore I included that in the video (only for a short time).
Thanks for the video sir
Awesome explanation of the concepts
But if we try to do in the 2nd method ,what if the graph has no cycle sir?
Like for example [[1,3],[1,4],[2,4]]
It has no cycle
We are just concerned about finding if any odd length cycle exists. Every other case will yield answer as TRUE (including no cycle case offcourse).
@@techdose4u Thank you sir
That means that a graph with no cycle can be bipartite all the time sir?
can u tell me which app are using to draw ? XD
sir u are really the best
Thanks for the video...
Welcome :)
what is software used as blackboard
Sir How long have you been studying DSA??
You have a great knowledge of DAA..
Hoping For You To Get 1 Million Subscribers Soon..❤❤
Thanks. From the past 3 years continously.
U explain well
But also tell us about urslf
Ur life journey
Later bro 😅
I don't understand what is wrong with the method I use. I passed 50/ 70 tests but seem to fail at larger cases. I didn't use dfs/ bfs, I just simply sort the input array and loop through each array to color it. I don't know why this logic fails. Can you please explain to me ?
public boolean possibleBipartition(int N, int[][] dislikes) {
if(dislikes == null || dislikes.length == 0) return true;
int[] color = new int[N + 1];
Arrays.sort(dislikes, (a,b) -> (a[0] - b[0]));
for(int[] dislike: dislikes){
int people1 = dislike[0];
int people2 = dislike[1];
if(color[people1] == 0){
if(color[people2] == 0) color[people1] = 1;
else{
color[people1] = color[people2] == 1? 2: 1;
}
}
if(color[people2] == 0){
color[people2] = color[people1] == 1? 2: 1;
}
if(color[people2] != 0 && color[people2] == color[people1]){
return false;
}
}
return true;
}
WE ARE USING UNDIRECTED GRAPH FOR BIPARITITE GRAPH
it's ... mind blowing
😅
sir the solution using 2 maps/sets will not give correct answer for cases where we will have a pair whose not in any group yet...so where we will insert the values of that pair in which set ??
How many cases did you pass using that method?
@@techdose4u 40/66
I will share the map code instead.
@@madhavsahi7400 I faced the same USING SET
Great man 👌
Thanks :)
why you haven't use directed graph??
What if two nodes in the same set are connected and they can form even edges
That can never happen because all pairs are unique.
@@techdose4u let two sets be 1,2 and 3,4 now they form even pair ,now consider 1,2 are connected and 3,4as well so again they form even pair edges but in this case it is not bipartite graph
the first method will not work please eveyone who is trying to do it with 1 st method then do not do it with 1st method
There is a solution with method 1. Have a look at PINNED comment.
i tried to solve this problem using DFS but i got an error "Stack overflow" , i cant understand what i did wrong there i'm doing almost same like you.
I also have a little request , can you please just take few minutes in your next video and explain how to code in leetcode , I've seen you sometimes you declare vectors and variables in the constructors and sometimes you just pass everything in the function as an argument , Can't we declare globally?
BTW your videos are great sir, you are doing a great Job
You can use global but I avoid using it.
@@techdose4u I just passed the adjacency list and vector as a parameter to my dfs function and it worked. Defining global was a problem I think.
Thank you
Here I am watching this video today on May 27
Yes I want to be a software engineer at faamg
bro code not working its giving error at adj[dislikes .... whats the problem there
10
[[4,7],[4,8],[2,8],[8,9],[1,6],[5,8],[1,2],[6,7],[3,10],[8,10],[1,5],[7,10],[1,10],[3,5],[3,6],[1,4],[3,9],[2,3],[1,9],[7,9],[2,7],[6,8],[5,7],[3,4]]
can you please explain this test case. i solved it using two sets and they are expecting true for this while my answer is false.
upto [5,8] person 1 and person 2 are in same set so when we check for [1,2] it should return false. but why they are expecting true for it?
It's because when you process element [2,8]. This is the resulting sets: S1={4,2,} & S2={7,8}.
Similarly, when you reach element [1,6] both 1 and 6 are not present in either set. So you Set would have been S1={4,2,9,1} & S2= {7,8,6}. So when you process element [1,2], it returns false as both the numbers are present in same set i.e, S1.
But if at the time of processing [1,6] if 1 is kept in S2 and 6 in S1, the resultant sets would have been S1 ={4,2,9,6} & S2 = {7,8,1}. So on processing [1,2], this would return true as it possible to place them in separate Sets.
So using the 1st (Set/Maps) approach solving this question is tricky. Try implementing 2nd approach.
Can you please tell how to solve this problem
Means to solve this typ of difficulty
@@muskaangupta4920 You can check the Python Code attached in the 1st Comment.
This is the case for even length cycle. You need to find if the graph has odd length cycle. This must be Test case no 39 where most people got stuck 😅 See the PINNED comment.
thanks alot
Welcome
Code Link : techdose.co.in/possible-bipartition/
will the set approach give time limit error?
No but some testcases fail.
I done using this way. The problem with this is if both elements are not there in two sets then the problems comes that is in which set we should place which element??
I have posted the link to a working code using SET in python. Follow PINNED comment.
I used the first method ,but when we find something like if we put 5 in v rather than u it will be true,
but result false, can you share a code for first approach?
class Solution {
public:
bool possibleBipartition(int N, vector& dislikes) {
vector g1(N+1,false);
vector g2(N+1,false);
for(int i =0;i
Some test cases are not getting passed using first method
@@rohithkumartangudu4664 maybe it can be solved , but I can't get last case in else statement
@@fatimajaffal9843 can u provide the code??
Follow the CODE link in PINNED COMMENT.
Do you upload solutions in java
Please find java solutions on leetcode discussions.
thanks
Thanks ☺️
Thankyou sir
Welcome :)
The first approach will not work for this testcase.
10
[[1,2],[3,4],[5,6],[6,7],[8,9],[7,8]]
Is disconnected bipartite graph possible?
Yea. Consider (1,2),(3,4). They are disconnected and have 2 components.
@@techdose4u thanks. I had another question too. I am a bit noob in coding.
what is the use of N in your bipartite function?
why you take size N+1? why it is not N?
It is just my habit. Better be safe than sorry 😅 Sometimes nodes start from 1 and sometimes from 0 and so most of the times I end up writing N+1 instead of N.
🔥❤️
😊
The map solution doest work for some test cases I have tried...can you provide the solution of map approach plz...
i tried with the first approach but it is falling, code is written his way I guess it should not fail, can you please check
public static boolean possibleBipartition(int N, int[][] dislikes) {
HashSet set1 = new HashSet();
HashSet set2 = new HashSet();
for(int i=0;i
Can you please match with the CODE I PINNED. Then let me know.
boht badiya
Thanks :)
Solution can be found at github.com/Ankur-Jat/leetcode-maychallenge/blob/master/week4/day28PossibleBiratrite.py I'm maintaining a github repo for leetcode challenges. Please show some love.
Just need to find cycle in a undirected graph
That won't work. Need to verify if graph is bipartite.
I did that ..but it doesnt work...Bipartite is solution here
you also need to check the no of nodes in that cycle .if it is even then return true else return false
Ab graph se darr ni lagta sahab
😂
Bro! The first approach you taught will not work, did you tried that?
Here is my code:
static class node {
int x;
int y;
public node(int x, int y) {
this.x = x;
this.y = y;
}
}
public boolean possibleBipartition(int N, int[][] dislikes) {
if (dislikes.length == 0) return false;
ArrayList list = new ArrayList();
for (int i = 0; i < dislikes.length; i++) {
list.add(new node(dislikes[i][0], dislikes[i][1]));
}
HashSet set1 = new HashSet();
HashSet set2 = new HashSet();
for (int i = 0; i < list.size(); i++) {
if (set1.contains(list.get(i).x)) {
if (set1.contains(list.get(i).y)) return false;
set2.add(list.get(i).y);
} else if (set2.contains(list.get(i).x)) {
if (set2.contains(list.get(i).y)) return false;
set1.add(list.get(i).y);
}
else if(set1.contains(list.get(i).y)){
if (set1.contains(list.get(i).x)) return false;
set2.add(list.get(i).x);
}
else if(set2.contains(list.get(i).y)){
if (set2.contains(list.get(i).x)) return false;
set1.add(list.get(i).x);
}
else {
set1.add(list.get(i).x);
set2.add(list.get(i).y);
}
System.out.println(set1 +" "+ set2);
}
return true;
}
Someone else tried and passed. You need proper conditional statements for that. I dint explain them. I just gave a hint.
@@techdose4u You can check my code also, and I can tell you where it fails
How many cases did you try?
Map was only failing for multi-component case. Test case no 66.
@@techdose4u 40 / 66 test cases passed.
Can anyone provide java code using 1st method??
Search it on leetcode discussions. You might get it.
@@techdose4u It is not there i already searched in discussions.
If algorithm is art u r Picasso of it.
❤️