Official
D - Neighbors Editorial by en_translator
Every person can be next to at most two people. Therefore, if any person appears three or more times in the conditions, then the answer is No
. This can be easily checked in a total of \(O(N+M)\).
Also, if there is a condition which forms a loop, like \((A_i,B_i)=(1,2),(1,3),(2,3)\), then the answer is also No
. This can be checked in a total of \(O(N+M)\) time with Union-Find, BFS, or DFS.
Conversely, if the two conditions above are not violated, then the answer is determined to be Yes
(without actually lining up!), so the problem has been solved.
posted:
last update: