Can somebody help me how to approach and think towards Wierd Problem (Problem code:BITREE) of CodeRush problem?
Problem Link:CodeChef: Practical coding for everyone
Thanks in Advance!!!
2 Likes
For counting bipartite graphs, an easier problem is to count graphs where the constraint that every vertex should be part of atleast one edge, only applies to one of the two parts. In that case you will just have to map each vertex in one part to some non empty subset of vertices in the other part.
Let’s pick one of the two parts, say, the part with M vertices, we will count the number of graphs in which every vertex of this part has atleast one edge. This is easy to count, the answer will be (2^N - 1)^M . But this also counts the graphs in which some of the vertices in the part with N vertices don’t have any edges, these are invalid graphs.
An invalid graph is a graph in which some non empty subset of vertices in the part with N vertices does not have any edges. You can use inclusion exclusion to count invalid graphs : C(n,k)*(2^k-1)^M*(-1)^k summed up over k = 1,2,…n.
1 Like