aya1909's blog

Total no. of distinct cycles in undirected graph
By aya1909, history, 5 months ago, In English

How to count total no. of distinct cycles in an undirected graph. Graph may be disconnected. Constraints: 0<= no. of nodes <=10

Answer for given image is 7

 
 
 
 
  • Vote: I like it
  • -32
  • Vote: I do not like it

Comments Comments (6)
»
5 months ago, # |
  Vote: I like it +4 Vote: I do not like it

Number of nodes is very small, so a brute force solution should work in O(n * n!).

→ Reply
  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    what is that brute force solution?

    → Reply
  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    actually no. of nodes can be upto 20

    → Reply
    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      In this case you can make a dp solution in O(n^2 * 2^n) (dp[mask][i][j] is 1 if there exists a path from i to j that contains all positions in mask, you can then loop over all of these and check if one of these completes the cycle)

      → Reply
      • »
        »
        »
        »
        4 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        it require more than 4*10^8 space.is that possible?

        → Reply
        • »
          »
          »
          »
          »
          4 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          solve individually for each i value (store the amt of cycles for each length so we can divide by that length later), then you cut down on memory

          → Reply