Covering a directed graph with particular requirements I'm actually trying to solve a task from an old OII (Italian national pre-IOI competition) in which I'm given an unweighted directed graph $G$ with $N$ vertices and $M$ edges and I'm asked to find a set of vertices $S$ which satisfies these conditions.
If we call $S^1$ the set of vertices that can be reached by crossing a single edge from any of the vertices in $S$, there can't be any vertex in both $S1$ and $S$.
Then we call $S^2$ the set of vertices that can be reached by crossing a single edge from any of the vertices in $S^1$.The set $S$ is a solution to this problem only if every vertex in $G$ is part of at least one of the sets above.
Couldn't think of anything better than an $O(2^n)$ solution, which leads to TLE. I'm given a time limit of 3 seconds, with $N &lt; 1000$ and $M &lt; N(N-1)/2$.

Something I realized is that I have to consider each different connected part on it's own and some vertices simply must be part of $S$ (if there are no edges starting from another vertex that reach them), but this assumptions didn't help much. 



I apologize for my english and my poor computer science knowledge, I'm sure some parts should be reformulated but I couldn't find the right words to do that.
This problem is solvable if you have studied computer science, know standard graph problems, can spot a relationship to one of them, and then diligently study what is known about algorithms for that sort of problem.

If this immediately makes you think that it sounds related to some standard, well-known graph algorithm problem (call it Problem X), then go read about what is known about algorithms for Problem X and variants of Problem X.  You'll soon find an existing algorithm that can be adapted for this.

If you can't spot any relationship to any graph problem you already know, then you should spend more quality time studying an algorithms textbook.  Pick a good algorithms textbook and read it through cover to cover.



Alternatively: What algorithm design paradigms do you know?  For each paradigm you know of, try to find an algorithm of that type.  You should be able to find one for this.



I'm not going to say more than this.  It's your exercise, so you should have the joy of finding the answer on your own; I don't want to take away from that.  Also, practicing problem solving on your own is the best way to strengthen your problem-solving skills.  If you just read someone else's solution, you won't learn nearly as much.