1. Answer always exists.
2. Use DFS for all unmarked vertices and mark them: if current vertex is marked as x, all next must be marked as (x + 1) % 2. (0->1, 1->0)
3. Then just print all vertices marked by 0 (or 1).

Edited by author 26.06.2010 04:17

I think, it doesn't need to use DFS. If the edge hasn't incident edges that belong to the first team, we add this edge to the fisrt team. That's all:)

If someone has no friends, there is no answer !!

Thanks, you very helped me)