Possible Bipartition | Bipartite graph | Graph coloring | Leetcode
ฝัง
- เผยแพร่เมื่อ 8 ก.ย. 2024
- This video explains a very important programming interview problem which is to find if we can divide all the incompatible persons into 2 different SETs.This is a very important problem for FAANG companies.The problem is based on finding possible bipartition.In case we have a possible bipartition then we will return true otherwise false.I have given 2 methods to solve this problem. The first one is just an idea about how to solve this using two MAPs or two SETs.The second approach is by using the classical bipartite graph algorithm.I have explained the intuition for solving this problem using graph algorithm.I have shown how this problem is reduced to just finding if a graph is bipartite then just return TRUE saying that it is possible to divide the incompatible persons into 2 different SETs.I have also shown how we canuse the graph coloring algorithm to solve this problem using 2-colors method of coloring graph. We have used only 2-color method because this is used to find if we have an ODD cycle length or an EVEN cycle length.Since, a bipartite graph never have an ODD length cycle, so, if we find any ODD length cycle then the graph will not be bipartite and hence it will not be possible to divide all incompitable persons into 2 different SETs.I have shown the working of algorithm followed by CODE walkthrough in C++ at the end of the video. CODE LINK is present below as usual. If you find any difficulty or have any query then do COMMENT below. PLEASE help our channel by SUBSCRIBING and LIKE our video if you found it helpful...CYA :)
=================================================================
INSTAGRAM: / surya.pratap.k
LinkedIn: / surya-pratap-kahar-47b...
=================================================================
CODE LINK: gist.github.co...
SIMILAR PROBLEMS:-
Detect cycle in an undirected graph | Graph coloring method: • Detect cycle in an und...
Detect cycle in a directed graph: • Detect cycle in a dire...
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 :)
Thank you, India, for tech dose! Absolutely Bad Ass and MUCH appreciated, if only for throwing Bill Gates out on his ugly ass. Much LOVE, from America!!!! Thank you, Tech Dose!!!!!!!!!
😅 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 :)
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.
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.
I am sure you will be having more than 1 million subscribers.
Splendid explanation 👌
Very soon.
Thanks for motivation :)
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 :)
In-depth, precise and very calm explanation.
Why is this the best series i have ever watched?
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 :)
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.
Learned a lot from this video
Your content is really good. Continue making such video with clear and concise explanation.
Yes I will :)
Thank you for such a clear and concise explanation.
Thanks :)
a lot of concepts covered in a single problem. very well explained :-)
Thanks :)
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.
Always clear cut explanation ♥️
Thanks :)
Thanks for this video. Really helped in understanding the concept.
Welcome :)
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.
Thank you very much for a very clear explanation. I'm still not good solving graph problems
Keep practicing and learning.
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.
Great Explaination!
Thank You!!
Welcome
One thing i would like to add up the graph at 7:34 is undirectional as if a hates b,b also hates a
U just nailed it as always .....keep it up👌👌💥
Thanks
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.
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
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].
thanks dude, great explanation
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
👍
Gadar gadar gadar🔥🔥🔥
😀
Really Great Explanation. Thank You!
Welcome :)
B 1.2 CR, S 1.3 CR J 39L
Thank you so much for a detailed explanation
Welcome :)
amazing explanation
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
Best teacher ever!
Thanks
You are simply awesome!
😅
great explaination buddy!!
Thanks
Best Explanation on this Topic I got so far 🙌
Thanks
sir u are really the best
best explanation ever!
Thanks :)
taking a boolean array instead of map and set will improve runtime
Yes.
great explanation !! thanks a lot.
Welcome :)
This channel is boon for Leetcoders!
😅 :P
sir please solve using Union Find too.
I will try sometime later :)
Very nice explanation 👌👌
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
Thank you so much Surya Sir
Welcome
please make a clear video on Generate all the binary strings of N bits and how the code is working. Please 🙏
thanks alot
Welcome
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!!!
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?
Why we are declaring 'adj' size and 'color' size as n+1?
thanks
Thanks ☺️
Nice explanation!
Thanks :)
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.
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.
Thanks for the video...
Welcome :)
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
It is a very simple problem. This video makes it complex, especially the bipartition graph section. Hate it!
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).
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.
Great man 👌
Thanks :)
U explain well
But also tell us about urslf
Ur life journey
Later bro 😅
Nice Work bro!!!
Thanks
Yes I want to be a software engineer at faamg
🔥❤️
😊
The first approach will not work for this testcase.
10
[[1,2],[3,4],[5,6],[6,7],[8,9],[7,8]]
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;
}
Thankyou sir
Welcome :)
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
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
bro code not working its giving error at adj[dislikes .... whats the problem there
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.
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.
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.
why you haven't use directed graph??
can u tell me which app are using to draw ? XD
what is software used as blackboard
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.
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...
boht badiya
Thanks :)
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.
Do you upload solutions in java
Please find java solutions on leetcode discussions.
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.
If algorithm is art u r Picasso of it.
❤️
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?
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.
Ab graph se darr ni lagta sahab
😂
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
Code Link : techdose.co.in/possible-bipartition/
did anyone find a line in this question which specifies that the graph can be disconnected? got 1 WA just because of this.
Yep. That's why it can be multi component 😅
@@techdose4u I checked the problem again, but didn't find the statement which refers to "the graph can be multi-component".
Consider this: (1,2),(3,4). If you draw adjacenecy list for undirected graph then you can see that it has 2 components. Each having 2 nodes.
I agree with you , but problem statement didn't clarified this.
@@Amit_Kumar_1999 unless it says we shouldn't assume it is single component