I tried to solve this problem but couldn't find a working solution with less than O(N2) time complexity. I would appreciate if someone could give me a hint to the solution.
Iterate through the nodes, then for each node you need to check two cases:
- item If node u has two edges of opposite direction then the flow can not come from one of these two edges, so you should mark all nodes that come through these two edges to u as bad.
- item if node u has two edges of the same direction then the flow should come to u through one of these two edges, so you should mark everything other than the nodes coming through these two edges as bad.
Now the remaining part is to figure out how to mark the bad nodes efficiently using DFS. Let me know if you need help.
Iterate through the nodes, then for each node you need to check two cases:
- item If node u has two edges of opposite direction then the flow can not come from one of these two edges, so you should mark all nodes that come through these two edges to u as bad.
- item if node u has two edges of the same direction then the flow should come to u through one of these two edges, so you should mark everything other than the nodes coming through these two edges as bad.
Now the remaining part is to figure out how to mark the bad nodes efficiently using DFS. Let me know if you need help.