aya1909's blog

Total no. of distinct cycles in undirected graph
By aya1909, history, 6 years 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

»
6 years ago, hide # |
 
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
  • »
    »
    6 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    what is that brute force solution?

    → Reply
  • »
    »
    6 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    actually no. of nodes can be upto 20

    → Reply
    • »
      »
      »
      6 years ago, hide # ^ |
       
      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
      • »
        »
        »
        »
        5 years ago, hide # ^ |
         
        Vote: I like it 0 Vote: I do not like it

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

        → Reply
        • »
          »
          »
          »
          »
          5 years ago, hide # ^ |
           
          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