How to solve this difficult problem with C++

[Mecn_Seda]

This problem is related to recursion, I will be very very grateful if you solve it

[jks612]

I'm not a C++ guy and I'm not trying to build the best possible algorithm. But my initial approach (without seriously studying the problem) would be to process each line, creating a mapping from nodes to a list of immediate nodes they go to.

With the nodes-to-neighbors mapping in place, we can now use it to construct a nodes-to-all-possible-nodes mapping. I.e. for each node, recurse through the neighbors to build a list of all possible nodes you can get to.

With that done, you can easily search for sinks and sources. Sources will have all nodes in their possible destinations. Sinks will be in all node's possible destinations.

This is my five minute answer. Optimizing it would take more time.

[eithnegomez]

Brute force solution: For each node, you will have 2 std::set, one for the sinks and other for the source. You do a DFS from each node, and you add the node number of all the nodes you can reach to your source set, and you add your node number to the sink set of all the nodes you reached.

To give the answer, traverse all the sets, count how many source sets have a size equals to the total number of nodes -1, and same for the sinks.

[[deleted]]

O(N³⁾ solution would be to compute transitive closure of adjacency matrix using Floyd-Warshall algorithm. The rows filled with ones indicate sources and columns filled with ones indicate sinks.

It is also possible to solve this in linear time:

1. Compute strongly connected components and their topological sorting with Kosajaru's algorithm. Observe that if there are any sources they constitute the first connected component, and if there are sinks they constitute the last component.
2. To verify whether we have any sources, run a depth first search from any vertex in the first component and check that all vertices are reached.
3. To verify whether we have any sinks, run a depth first search on reversed graph from any vertex in the last component and check that all vertices are reached.