Leetcode 3910 | Count Connected Subgraphs with Even Node Sum | Biweekly contest 181

追加: 2026-05-05

[00:00:00]Hello, in this video let's discuss third question of today's contest. You are given a underrated graph with the nodes from 0 to n minus one. Node i has a value of v of i which is either 0 or 1.

[00:00:10]The edges of the graph are given by 2D edges u of i v of i. For non- empty subset of nodes in the graph, we consider the induced subgraph of s general as follows. We keep only the nodes in the s. We keep only the edges whose two end points are both in. return an integer representing the number of non- empty subjects such that the graph which we form is connected and the sum of node values is even and the constraints are length is only the number of nodes are only up to 13 and v of i is up to 01 it means only 01 and the edges are up to n into n minus 1 by 2 it means it can be a complete graph and then the edges of i is u and va and all the edges are distinct so this is not tough this is a very straightforward one but the only thing to know is how to traverse each and every subset. So the first thing right the number of nodes is only up to 13. So what does that mean? It very simply says that we have to loop through every subset.

[00:01:06]So if we have 13 nodes then what are the total number of subsets that we can form? It is 2^ 13 because for example let's say we have four nodes and we can try to remove one like for example if we are trying to find a new graph with few nodes. Let's say we are trying to find a new graph with X nodes. Then we can try to include one in X or not. Then we can try to include two or no. We can try to include our node three and we can try to include or skip four. So for every node we have two choices. One to include that in the sub in the graph that we are considering. The other thing is don't consider that in the graph. So 2 into 2 into 2 into 2. So I have 16 number of graphs that we can form. So one graph with only one, one graph with one and two and other graph with three, other graph with three four three four and so on. So in this way we have 16 number of graphs that we can form given four nodes and that is simply two power n. So given n number of nodes the number of graphs that we can find is 2^ n. Now let's say uh so how to traverse this 2^ n.

[00:02:05]So we can try to use a bit mask right.

[00:02:07]So what is bit mask? So for example let's say we are trying to find a graph with 1 to 4 5. So how to store this information such that now we in a graph that that have nodes as 1 to 4 5. We can't show in the vector, right? We can't show in the vector that the nodes are 1 2 4 5.

[00:02:27]So, is there any way that we can know that these are the four nodes that are included in the current graph that we are traversing? Yes. So, now the numbers are only one only 13. So why don't we try to represent the nodes which are included in the graph that we're considering as one and the nodes which we are not considering in the present graph as zero. For example, let's say we have 1 0 1 1 0 0 1 0 1 2 3 4 5 6 7 8 10 11 12 13. Let's say we have this 13 bit number, right? So this is just 13 zeros and ones now. So what does this mean? So for example, for example, it is the list index. So this is the let's say this is the index zero. So coming to now for now let's assume this is a string. So given a string so zero index is one. So what does that mean? It means that in the graph that we are considering zerooth node is there that's why the bit is one right for example we have let's say we have only four nodes and now the graph which we are trying to find is one two right? We have only four nodes and the graph that we are trying to find is only one two. So how to represent this? So how to represent that in the current graph that we are considering we only have nodes one and two. So if we are having the nodes one and two then three and four are not there. So one and two are there and three and four are not there. So why can't we represent something like a some string like this saying that if the number is equal to one if the index is equal to one like if you're at index I and if that index value is one then that node is current is present in the graph that we are considering. So if the graph is 1 two then only one and two are considered in the present graph that's why the string that is formed is 11 1 0 0. So in the node one is in the graph that we are considering node two is in the graph that we are considering node 3 is not there node four is not there. So from this we can try to like given a string right given a 13 length string we can easily find what are the nodes that we are considering in the present graph and what are the nodes that we are not considering.

[00:04:31]In this way we can try to find but instead of string we can try to store integer itself because the numbers are only from 13. So the highest number is 2^ 13 which is around around uh 8,000 right around 8,900.

[00:04:46]So 8,90. So let's say the numbers are only from 1 to 890. So if we take any number from 1 to 8 090 let's take 1345.

[00:04:56]So if we try to represent this in the number in the binary representation then we'll get some zeros and some ones. So what does that mean? For example, let's say we got 1 0 1 1 0. So what does this mean? It means in the bitwise this is the least MSB like this is the least bit and this is the highest bit. So this is the zeroth bit. This is first bit this is second bit. This is third bit. This is fourth bit. So if the bits 1 2 4 are set. So what does that mean? It means that in the graph that we are considering right in the subset that we are considering the nodes present are only 1 to four 3 four are not present. Now if we know 1 to four nodes are present then what can we do then we can try to find a graph where only 1 to four are included that is what said in the question. So after finding a subset the induced graph is connected and the sum of values is even.

[00:05:45]So after getting a subset now after giving subset so what does that mean? It means now we are in now we are finding if the sub graph by considering one to four nodes is good or not. So how to find if this is good or not. So firstly given the edges now form a new graph which will contain only 1 to four in edges. For example initial graph says that 1 two are connected 1 three are connected 1 four are connected four 7 are connected. Now the nodes that we're considering in the graph is only 1 to four. So 1 to four. So connect one and two. 1 to three. We don't have three in the current graph. So skip this edge. So we have 1 four. So now connect 1 four.

[00:06:25]We have 4 7. Do we have seven in this?

[00:06:27]No.

[00:06:29]So the new graph that we have is 1 to four. Now given a graph, this will be a good graph. If the sum of values of all the nodes in this is even and this should be connected. So this is straightforward, right? Given a graph, we know how to find if it is connected or not and how to find if the sum is even or not. So this is very easy. We can do a simple BFS.

[00:06:51]So now we can loop through all the values from mask is equal to 1 to 2^ n minus one. So what does this mean? It means we have to like it is given that we have to consider the non- empty number of subsets like non- empty subset. So if you start from zero all the nodes are zero. It means we are not containing any node but that is empty.

[00:07:09]So we don't want that. So we'll start from mask one and at every mask at every mask sum x we will try to extract that bits in the binary representation and then if the bit is one then we'll try to include those in the graph and then we will try to construct a graph which contains only these as the nodes and edges and then after getting that we will try to find if this is connected or not and if this connected we will check if the sum of values of this is even or not. If yes then we'll add else zero.

[00:07:40]Now initially we will find the adjgency list because this is under graph. So add x of0 to x of 1 and then u2 v2 just simply like a u2 v and v2. Now after this loop through every mask so mask is equal to 1 to 2^ n minus one. So why 2^ n minus one?

[00:08:00]Because if you are considering all the nodes right for example if you have 13 nodes and if you are considering all the nodes in the graph that we're considering then it will be 1 1 1 1 and that is simply 2^ 13 minus one. So the least subset that is one because we consider at least one node in the graph.

[00:08:16]So the least is one and the highest is 2^ 13 - 1. So look through each and every mask in this and then now find the like we have to find the first node which is included in the present graph. So, so why only for one? Let's say, let's say we have 1 2 4 5 in the present mask, right? So, if we just find one number which is included in this graph, then what can we do? Then we can simply initially itself we found the agency list. That's why we will start with one and then we will loop through all the edges that are connected to one and then let's say these three are the nodes initially connected to one. Now, we'll check if this node is set in the mask that we are at. If yes, this is a node that we have to consider. It means that in the present graph. So add this into Q and then mark this as V state.

[00:09:06]And then we'll come to this node and we'll check if this is set in the mask or not. If no, then we'll not consider this. We'll skip this because this is not good node. So we'll not consider and then we'll come to this and on. So just by finding one, we can start BFS. So initially just find start. So in the mask find the first bit where it is set.

[00:09:26]So loop through each and every i till end and then find the first start which has set. So if we find so if this is one it means i3 bit set in mask. So start is equal to i break and then start a q and then use a wed. So push the start vector into mark this wed and then we have to maintain two two things. The first thing is is the sum of all the nodes is even or not and second thing is is the graph connected or not. So simply store two values one as the count and then the second is sum. So firstly do the bfs get the present node pop the present node and then increment the node. It means we are counting the number of nodes that we like number of nodes which are present in the graph like like how many we are able to find from the BFS. For example, let's say we have graph 1 2 2 4 right 7. Now let's say the mask which we are considering as 1 4 7 as good nodes. Now if these are three nodes then what will be the graph that we have? You have 1 47 but either of these are not connected. That's why we will maintain like given a mask right given a mask we can know how many number of nodes that are connected in this mask which is simply the number of set bits for example if the mask has two nodes it means there will be two two ones in the given mask so by mask we can say how many numbers how many number of nodes that are actually in the mask so that is one thing let's say we got there are two nodes which are in the present mask then how to find if this is connected or not so initially we have one right initially we have we have some node and then we are doing the full BFS. So after completing the BFS, we will maintain the number of nodes that we traversed. So here let's start with one. Let's say we have one. So if we start with one, we are not considering any edge because there is no good edge that we are considered which is attached to one. So there is no good node. So we will not do anything and we'll break the loop because we can't do DFS, we can't do BFS. So that's why the count will be only one. So what does count is equal to one mean? It means we are able to get only one node but ideally there should be three nodes if there is one connected component. So just simply check if these both are equal or not. It means we have to loop we have to reach every node if we are starting from any node only then it should be called connected. So that's why maintain a count variable and then increment the nodes which we which we are which we are finding and then add the sum and loop through all the edges which are connected to you and then if this is in the present mask and if this is not wasted then visit this and then push into the cube and then after completion of whole BFS check if the number of nodes that we traversed is equal to the number of nodes which you have it means the number of connected component is one. If the component is one and sum is even then count answer because this is a good graph and finally return the answer. If you have any doubts comment below. See you in the next video.