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 : “

After solving above problem , I google but here what i found -
GFG article : “

My more optimised solution : “

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 -

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 .