RestingRajarshi's blog

By RestingRajarshi, 5 years ago, In English


Hi, I have been trying this problem, and I have an alternate solution to the editorial as follows:

Form a new graph, with nodes as (prevNode, currNode), to keep track of which node we are coming from. There will be an edge from (A,B) to (B,C) in the new graph if A-B-C is not a 3-cycle in the original graph. Now, after forming this graph, find a cycle in it. This will correspond to a cycle in my orginal graph too. Now i claim that in this cycle of my original graph, there will be no 3 consecutive nodes that form a 3-cycle, due to the constraint of edge on my new graph. So the cross edges that we will have will divide my cycle into sectors with more than 3 nodes. Hence outputting any such sector should be fine. However, I am getting WA on most of my cases. The code is printing "no", which i found was that it was indeed getting a cycle in the new graph but couldnt find such sector in my original cycle for some reason.

Can someone confirm if the solution is correct? (my implementation is not good so there is a high chance i am coding it wrong). And if its incorrect, can someone give a counterexample to either of the claims, 1) if there is a valid graph which does not give a cycle in my new graph, or 2) any cycle in my new graph will correspond to cycle in my original graph that will have sectors that are not 3-cycles

Thanks for any help.

my code

  • Vote: I like it
  • +1
  • Vote: I do not like it

5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by RestingRajarshi (previous revision, new revision, compare).