Блог пользователя Farsh_LE

Автор Farsh_LE, история, 21 месяц назад, По-английски

Hi codeforces

I was solving this problem:
You are given an undirected graph consisting of n vertices and n edges. It is guaranteed that the given graph is connected (i. e. it is possible to reach any vertex from any other vertex) and there are no self-loops and multiple edges in the graph.

Your task is to calculate the number of simple paths of length at least 1 in the given graph. Note that paths that differ only by their direction are considered the same (i. e. you have to calculate the number of undirected paths). For example, paths [1,2,3] and [3,2,1] are considered the same.

But I didn't notice that it has n edges (thought it had m edges which is given in the input), but I didn't find an answer better than n^2

so I want to ask , does anybody know a faster solution for the new problem(m edges )

Thanks!

  • Проголосовать: нравится
  • +8
  • Проголосовать: не нравится

»
21 месяц назад, # |
Rev. 10   Проголосовать: нравится +27 Проголосовать: не нравится

How do you solve this problem with n^2? I suspect that this problem can be addressed to the Hamilton cycle in some way.


Update :

No, it's more difficult than Hamilton. It's 『Sharp-P-complete』. There is no polynomial algorithm for this problem, and also no acceptable approximation algorithm.

reference : https://epubs.siam.org/doi/abs/10.1137/0208032

»
21 месяц назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

What if there is a cycle in the graph?

  • »
    »
    21 месяц назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    yes , if there is m edges there can be a lot of cycles, that's why I'm asking for a solution