AhmedOmani's blog

Graph Problem
By AhmedOmani, history, 17 months ago, In English

Hello guys, first of all, I am sorry for my bad English but I hope that I can reach my problem correctly

https://codeforces.net/gym/104030/problem/E

I faced this problem today and I spend a lot of time but I can't solve it. The problem says that you are given a graph and your task is to count the number of shortest cycles in the graph.

I was able to find the shortest cycle by the Dijkstra algorithm but I don't have an idea how can I count the number of this shortest cycle.

so, any ideas or hints?

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

»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Suppose the shortest cycle is of length $$$k$$$. Consider running BFS from some node $$$u$$$. This gives you distances $$$d_v$$$ to all other nodes $$$v$$$. Now consider edges between some pair of nodes $$$v$$$ and $$$w$$$ such that $$$d_v = d_w$$$ and $$$d_v + d_w + 1 = k$$$. Then $$$(v, w)$$$ is the edge which closes a cycle containing the node $$$u$$$, considering the construction of the cycle started from node $$$u$$$ with the BFS.

You can reason a similar result for even cycles, although it is a bit trickier.

→ Reply
  • »
    »
    17 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    so what about overcounting, if I am on the right path I think by this way for every node we will overcount the cycles, is it right? if it is how can I handle it?

    → Reply
    • »
      »
      »
      17 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      When doing BFS from node $$$u$$$ you ignore nodes $$$v < u$$$, guaranteeing that $$$u$$$ is the minimum node in the cycle you find. That way you will not overcount.

      → Reply