Reachibility #SCC #Kosaraju SPOJ : CAPCITY And TOUR

Basic Concept :

Find the nodes reachable from all other nodes or similarly if a node can reach all other nodes. We'll take the former as the standard problem. 

TOUR

Aakhir ye question chahta kya hai?

Find all the players that can win if there is a little corruption in the committee that decides the schedule.

Consider a directed graph where the nodes are the players and the edge denotes the player that can beat the other. 

Now the nodes that can reach all other nodes is the one that can beat all other players.

So the question boils down to finding the nodes that can reach all other nodes.

FINDING NODES THAT CAN REACH ALL OTHERS

Observations:

1. If a node can reach all other nodes, then all the nodes in that Strongly Connected Component can reach every nodes. 

2. Now after finding all the connected components, find the degree of incoming edges of each CC. Based on the number of CC with 0 in-degree, there can be 3 observations :

    2.1 0 CC with 0 in-degree

          

           Ok, think like this, there are two CC's A and B. Now we say that A can reach any other CC. Then A can reach B. BUT there cannot be a path from B to A as if there is a path from A to B and from B to A, then they are a part of the same CC. So if B is reachable from A, there can be only ONE path between them. So in-degree of A has to be 0.

  

         By this logic, 0 in-degree is a requirement for reachibility.

   2.2 More than 1 with 0 in-degree

         From the above mentioned logic, if there are more than one CC's with 0 in-degree, and suppose there is a CC that can reach all, then that CC has 0 in-degree. Now take A and B. A is the reacher and B is another CC with 0 in-degree. 

         Now here's the problem. If A can reach all, then it should also reach B ! But B has 0 in-degree i.e. no one can get reach the nodes in that CC, not even A ! Ergo, A can't reach all.

       

        Hence, there can't be a CC that reaches all if there are more than 1 CC with 0 in-degree.

  2.3 Exactly 1 CC with 0 in-degree

         Assume there is only one CC with 0 in-degree. So the rest of the CC's have more than 0 in-degree i.e. there is some CC that can reach it, and there is some CC that can reach it... and so on till the CC with 0 in-degree reach it.

         What I want to say is that, Say there are 4 CC's and D is the one with 0 in-degree. Let B can reach A and C can reach B and D can reach C. < D -> C -> B -> A >.

      Hence D can reach all. In general case, the CC with 0 in-degree can reach all others. Hence that CC is the one we are looking for !

 Summary 

 In this question look for the CC's with 0 in-degree. If they are 0 or more than 1, then no reachable CC exists. If exactly one CC exists, then all the nodes of that CC can reach all the other CC of the graph.

 CAPCITY

CAPCITY is almost exactly the same as TOUR.

ALGORITHM :

1. Apply Kosaraju's algorithm to find the strongly connected components. ( I've written a well detailed post on this algo before)

2. Calculate the indegree of each Connected Component.

        REP(i,1,n){
        for(auto it:graph[i]){
            if(comp[i]!=comp[it]) indeg[comp[it]]++;
        }
        }

3. Find the number of CC's with 0 in-degree.

4. If more than 1 or 0, then none exist.

5. If exactly one CC is there, then the print the number of nodes of that CC.

CODE :

http://ideone.com/FONff5