Shortest cycle in an undirected unweighted graph , can we do better ? (Graph problem 13)

I wanna find out the length of shortes cycle in graph , one approach is just do brute force , but time complexity is N2 ,

Question : “https://www.e-olymp.com/en/contests/16924/problems/175331

After solving above problem , I google but here what i found -
GFG article : “https://www.geeksforgeeks.org/shortest-cycle-in-an-undirected-unweighted-graph/

My more optimised solution : “https://ideone.com/hjaBe1

But as I said it is still N2 can we do something better , by using concept of LCA or something else ?

@galencolin @ssjgz @aneee004 @everule1 @spaanse

any idea ? @ssjgz

Just had a quick google, and can’t seem to find anything better :man_shrugging:

1 Like

one more doubt -

https://www.geeksforgeeks.org/shortest-path-with-even-number-of-edges-from-source-to-destination/

see in this we have to find the shortest even length path between source and destination,

But this above approach seems wrong, the test case which author takes when i take source as 1 and destination 2 then the code gives output 13 but it should be -1 .