Блог пользователя Empty

Can someone explain me this code?
Автор Empty, 12 лет назад, По-английски

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


Теги xor
  • Проголосовать: нравится
  • +12
  • Проголосовать: не нравится

12 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится
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 ). 
→ Ответить
»
11 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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

→ Ответить