PROBLEM LINK:
Author: Praveen Dhinwa
Tester 1 Goutham Kobakini
Tester 2 Arjun Arul
Editorialist: Praveen Dhinwa
DIFFICULTY:
Medium
PREREQUISITES:
bitmask dynamic programming
PROBLEM:
Given a directed graph G. Find number of vertex disjoint cycle covers of the graph modulo (10^9 + 7).
QUICK EXPLANATION
-
The most crucial part is to note that number of vertex disjoint cycle covers of a directed graph is equal to number of perfect matchings in the a constructed bipartite graph using the method stated in next section.
-
Finding number of perfect matchings in a bipartite graph can be done in \mathcal{O} (2^n n) time using bitmask dp.
-
Number of perfect matchings in a bipartite graph are equal to permanent of bi-adjacency matrix of the graph.
-
Find permanent of a matrix can be done in \mathcal{O} (2^n n) time using bitmask dp.
EXPLANATION
Create a bipartite graph
Assume graph G has total n nodes. Let us create a bipartite graph as follows. Both left and right side will have n vertices each. If there is an edge from u to v in the graph G, we will add an edge from u in the left part to v in the right part in the bipartite graph.
Example:
Let us take a example graph of 3 vertices.
Then the constructed bipartite graph will be following.
Number of vertex disjoint cycle covers in the graph are equal to be number of perfect matchings in the corresponding bipartite graph
We can prove both the sides quite easily.
Assume that we are given vertex disjoint cycle cover in graph G. Let us consider a cycle C of it. If it has an edge u, v, we will match u to v in the bipartite graph. In this way, we will generate a perfect matching in bipartite graph. Note that we will not match any vertex to more than one vertices because in the cycle cover, next vertex of a vertex is only a fixed vertex (as cycle cover is a vertex disjoint cycle cover).
Similarly, let us consider the reverse of the statement. You are given a perfect matching in corresponding bipartite graph. We can construct a cycle cover from that in following way. Start from vertex 1 to n in order in the left part of bipartite graph. Pick the current vertex u if it has not been added in cycle cover up to now. Now let us consider the matching edge ve u, v'. Then we will pick vertex v in left part and continue the same way. You can notice that we will create a cycle in the end. So we will add it to cycle cover and continue this way.
Note that you can also prove that this mapping is a one to one and onto mapping. So number of vertex disjoint cycle covers in the graph are exactly equal to be number of perfect matchings in the corresponding bipartite graph.
Finding number of perfect matching in a bipartite graph
We will use a bitmask dp here as follows. We will iterate over the vertices of left part in the order from 1 to n. Assume that currently, we are at vertex i. It means that we have matched all the vertices from 1 to i - 1 to some vertices in the right part. We will try to match i with some of non - matched vertices in the right part.
What information should we know to make sure that we don’t match current vertex i to already matched vertices in the right part?
We should maintain the set of matched vertices on the right side. As these sets will be subset of set of vertices \{1, 2, \dots n \}, we can make use of bitwise operations to store and operate on the set efficiently. So we will maintain an integer mask denoting set of matched vertices on the right side.
So our state of the dp will be (i, mask).
Now let us think about transitions. We can match the current vertex i to any of the non-matched verties on the right part. Let us see the pseudo code.
Pseudo code
int memo[n][(0 << n)];
int dp(int i, int mask) {
int &res = memo[i][mask];
// used for memoization. If res is equal to -1, means that information is not computed now.
if (res == -1) {
res = 0;
if (i == n) {
// all are matched, then it is a perfect matching.
res = 1;
} else {
// match i on left side to j on right side if j is unmatched.
for (int j = 0; j < n; j++) {
// check this vertex j is present in the set of matched vertices mask or not.
if (!(mask & (1 << j))) {
// Add the right side vertex j into set of matched vertices mask.
res += dp(i + 1, mask | (1 <= mod) {
res -= mod;
}
}
}
}
}
return res;
}
memset(memo, -1, sizeof(memo));
int ans = dp(0, 0); // it means that we are starting from vertex 0 on left side.
//No vertex on right side is matched up to now.
Time Complexity
State space of the dp is \mathcal{O} (n * 2^n).
Transition time for each state is \mathcal{O}(n).
So total time taken is \mathcal{O} (n^2 * 2^n).
Note that this solution will not pass in time. We need to reduce time by a factor of n.
Optimization by a factor of n
You can notice that instead of iterating over index i, we can iterate over all possible subsets of matched vertex on the right side. Then we will iterate for each non picked vertex i from 1 to n on the right part. Now the optimization here is that we will try to match vertex i only with vertex v where v = number of sets bits in current mask under consideration.
You can notice that in this way, we will consider all possible perfect matchings.
Pseudo Code
int numberOfPerfectMatchings(int[][] adj) {
int dp[] = new int[(1 << adj.length) + 5];
dp[0] = 1;
// number of ways of matching empty sets on the right set with left side is 1.
// It is base case of the dp.
for (int mask = 0; mask < (1 << adj.length); mask++) {
for (int i = 0; i < adj.length; i++) {
if ((mask & (1 << i)) == 0) {
dp[mask | (1 << i)] += dp[mask] * adj[Integer.bitCount(mask)][i];
if (dp[mask | (1 <= mod) {
dp[mask | (1 << i)] -= mod;
}
}
}
}
return dp[(1 << adj.length) - 1];
}
Time Complexity
External loop over mask will take \mathcal{O}(2^n) time. Inner for loop will take \mathcal{O}(n) time. Finding number of set bits in an integer can be found in constant time. Please see this amazing article for more discussion into it.
For having a good understanding of bitwise operations, please see following topcoder tutorial.
So overall time taken is \mathcal{O}(2^n n) which will easily pass in time.
Relationship between number of perfect matchings in the bipartite graph and permanent of bi-adjacency matrix
Number of perfect matchings in a bipartite graph is equal to permanent of bi-adjacency matrix of the graph.
Wikipedia states that “The number of perfect matchings in a bipartite graph is counted by the permanent of the graph’s bi-adjacency matrix, and the permanent of any 0-1 matrix can be interpreted in this way as the number of perfect matchings in a graph.”
So we will create an adjacency matrix of the bipartite graph (which is same as adjacency of the graph G).
Finding permanent of a matrix (theoretical discussion)
There is a straightforward way of computing permanent in \mathcal{O} (n * n!) time by trying all permutations.
Please see “Ryser formula section” of this link for solving this in \mathcal{O} (2^n * n) time. You can use earlier discussed bimask dp to solve the problem in same time too.
Time complexity
As discussed, time complexity required was \mathcal{O} (2^n * n).