I need to find algorithms for both undirected and directed graphs, with no assumption on them being connected. Also the algorithms must be $O(V+E)$, where the undirected one should not depend on $k$.
I have ideas for both, i'm just not very sure about the directed version, because I'm not sure on how to approach the correctness proof.
For the directed version, I thought about finding all the SCC's with two DFS runs, and then running a topological sort on the graph created by representatives from each SCC. Afterwards, i'll flip the edges and start a DFS from the end vertex. For every SCC node I visit i'll increment a counter by the number of nodes in the SCC I visited. If while vising a SCC node the counter shows $k+1$ nodes, all the nodes in the SCC will be added to the set. At this point the algorithm will go back as though we reached a leaf.
For the undirected version, I can just do run a BFS/DFS for every disconnected component to find all the connected components. If a connected component has exactly k+1 nodes, then all the nodes in that component belong to the set.
Any help regarding the directed version will be great, thanks!