Please read the new rule regarding the restriction on the use of AI tools. ×

duongquanghai08's blog

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

By duongquanghai08, history, 5 hours ago, In English

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

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

»
4 hours ago, # |
← 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
  • »
    »
    112 minutes ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    Shortest cycle length here $$$= 3$$$, not defined by only one back edge

    → Reply
»
105 minutes ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I think this can help you

→ Reply