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!
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
That is only true for a general graph. This graph has a special structure which allows an efficient solution.
You need to worry about your TOEFL scores.
Oh my bad didn't read carefully.
Ok , thanks a lot !
What if there is a cycle in the graph?
yes , if there is m edges there can be a lot of cycles, that's why I'm asking for a solution
Oops, I understood the problem incorrectly :)