Empty's blog

Can someone explain me this code?
By Empty, 12 years ago, In English

I couldn't understand this code for this problem used in Round #95 Div2. He used xor to create edges?


Tags xor
  • Vote: I like it
  • +12
  • Vote: I do not like it

12 years ago, # |
  Vote: I like it +8 Vote: I do not like it
x[v] stores information about all neighbours of v. But only for leaves (deg[v] == 1) we exacly know about vertex's parent in the tree. After deleting leaves and recalculation x ( (X^i)^i == X ) we can get parent of new leaves and so on...
About this problem after recursivly deleting leaves, only loop stay in graph(with ans[i] == 0 for each vertex i in cycle ). 
→ Reply
»
11 years ago, # |
  Vote: I like it +5 Vote: I do not like it

very good solution for detecting nodes of a cycle... Thanks for pointing this solution :)

→ Reply