Here is the problem statement
http://www.spoj.com/problems/CAPCITY/
The graph is directed. (If you need information about directed/indirected graphs go here)/ As you can see from constraints we need to figure out a N*LogN solution or something close to that. The first thing we wanna do is keeping a second graph with reversed edges. We need to loop over all the nodes and run a BFS in the following way. (We are looping over the graph with reversed edges). Initially we keep a mark array for the reversed graph. If the current node is unmarked we start a wave (BFS) from that node (in a reversed graph). If we reached all the edges that means that the current node can be a capital city and we need to launch another wave (BFS) in the initial graph and add all the nodes which are reachable from the current node to the asnwer list. We do the exact opposite( mark it as not capital) if on the reversed graph cannot reach all the nodes. MAKE SURE TO CHECK THE SOURCE CODE FOR OTHER IMPORTANT DETAILS
http://www.spoj.com/problems/CAPCITY/
The graph is directed. (If you need information about directed/indirected graphs go here)/ As you can see from constraints we need to figure out a N*LogN solution or something close to that. The first thing we wanna do is keeping a second graph with reversed edges. We need to loop over all the nodes and run a BFS in the following way. (We are looping over the graph with reversed edges). Initially we keep a mark array for the reversed graph. If the current node is unmarked we start a wave (BFS) from that node (in a reversed graph). If we reached all the edges that means that the current node can be a capital city and we need to launch another wave (BFS) in the initial graph and add all the nodes which are reachable from the current node to the asnwer list. We do the exact opposite( mark it as not capital) if on the reversed graph cannot reach all the nodes. MAKE SURE TO CHECK THE SOURCE CODE FOR OTHER IMPORTANT DETAILS
No comments:
Post a Comment