I am learning graph algorithms and I am confused why my code 326424345 failed in test 18 for the problem https://mirror.codeforces.com/problemset/problem/977/E?
I know that the problem can be solved simply by counting the degrees of all the nodes in a connected component. Count the component when the degree of each node is 2.
However, I wanted to know what is wrong with the logic: for each connected component, we find the size of the smallest cycle, if this size equals the number of nodes in the component, count the component. (The size of the cycle initially is number of nodes + 1, so that we don't count components without cycles.
Please help me in understanding the problem, I will be very grateful to you.
Auto comment: topic has been updated by TheMathEnthusiast (previous revision, new revision, compare).
Logically you are correct. Problem is in the implementation. You are using the concept of in-time (in dfs) to calculate the length of the smallest cycle, which is wrong. For example for the testcase:n=5,m=5,edges[5]={{1,2},{2,3},{3,5},{3,4},{4,1}}. Your code will first visit 5 from 3 and then it will visit 4, leading to incorrect cycle length calculation.
Yes got it thanks!
i think this logic fails when theres a component like lets say edges are {1 2} {1 3} {2 3} {2 4} {3 4}
smallest cycle size is 3 but there's a larger cycle which connects all nodes in one cycle.. try largest cycle imo that should work ..correct me if im wrong
ahh looked at the problem again the cycles dont contain an inner edge...yeah this would work..but i'd be curious if that wasnt the case..will the longest cycle size work?