Count Ways to Place Non-Overlapping Edges to Connect All Nodes in C++

Suppose we have a number n that is representing the number of nodes that are placed circularly. We have to find the number of ways we can place n / 2 edges such that every node is connected by an edge, and that edges does not intersect with each other. If the answer is very large then return result mod 10^9 + 7.

So, if the input is like n = 4, then the output will be 2, as we can group them like below −

To solve this, we will follow these steps −

• Define an array dp of size (n/2 + 1)

• dp[0] := 1, dp[1] := 1

• m := 10^9+7

• for initialize i := 2, when i <= n / 2, update (increase i by 1), do −

  • high := i

  • dp[i] := 0

  • for initialize j := 1, when j <= high / 2, update (increase j by 1), do −

    • dp[i] := (dp[i] + (2 * dp[j - 1] * dp[high - j])) mod m

  • if high % 2 is non-zero, then −

    • dp[i] := (dp[i] + (dp[(high - 1) / 2] * dp[(high - 1) / 2])) mod m

  • dp[i] := dp[i] mod m

• return dp[n / 2]

Example  

Let us see the following implementation to get better understanding −

 Live Demo

#include <bits/stdc++.h>
using namespace std;
int solve(int n) {
   vector<long long> dp(n / 2 + 1);
   dp[0] = 1;
   dp[1] = 1;
   int m = 1000000007;
   for (int i = 2; i <= n / 2; i++) {
      int high = i;
      dp[i] = 0;
      for (int j = 1; j <= high / 2; j++) {
         dp[i] = (dp[i] + (2 * dp[j - 1] * dp[high - j])) % m;
      }
      if (high % 2) dp[i] = (dp[i] + (dp[(high - 1) / 2] * dp[(high - 1) / 2])) % m;
         dp[i] %= m;
   }
   return dp[n / 2];
}
main(){
   int n = 4;
   cout << solve(n);
}

Input

4

Output

2