Hello guys, first of all, I am sorry for my bad English but I hope that I can reach my problem correctly
https://mirror.codeforces.com/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?
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.
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?
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.
yeah yeah got it thanks a lot !