duongquanghai08's blog

shortest single cycle in an unweighted graph n<=1e6

By duongquanghai08, history, 19 months ago, In English

shortest single cycle in an unweighted graph n<=1e6

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (7)
| Write comment?
»
19 months ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it

Is it a directed or an undirected graph?

If it's an undirected graph, you can construct a DFS Tree, and every back-edge defines a cycle

→ Reply
»
19 months ago, hide # |
← Rev. 2  
Vote: I like it +5 Vote: I do not like it

I think this can help you

→ Reply
»
19 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

orz dequy hai

→ Reply
»
19 months ago, hide # |
 
Vote: I like it +26 Vote: I do not like it

It can't be solved in better than $$$O(nm)$$$, where $$$m$$$ is the number of edges.

https://en.m.wikipedia.org/wiki/Girth_(graph_theory)#Computation

→ Reply