WA in SPOJ-BOTTOM

general
, , , ,
1

In the question http://www.spoj.com/problems/BOTTOM/ i am regularly getting a wrong answer.
I am trying to modify Targans Algorithm for Connected Components. This is my code
http://ideone.com/Qe6BmJ
My logic is to modify Targans algorithm

  • Using Targans algorithm. When we start dfs in a TREE. Now whenever there is a pop in the stack (global) in my code it means that these elements constitute a Connected Component but the elements before it in the stack cannot be sink since some of its descendants have already been removed .
  • Now before moving to the next tree in the bottom based recursion we clear the whole stack so that it works.
    Could anyone please supply me with counter cases or my flaw.
    Thanking you in advance .
2

I tried but couldn’t understand your approach completely, so I’ll start from beginning, just assuming you know the standard Tarjan’s algorithm

Imagine that you replace each strongly connected component (SCC) by a single node, and there is an edge from one SCC node to another if there was an edge from some vertex in first SCC to some vertex in the other. Now, this graph will be a DAG (Directed Acyclic Graph). You need to find the sinks of this graph.

So how to proceed (without actually constructing the above DAG)? Apply Tarjan’s algorithm and for each component also assign it’s component number. Now process every edge in the graph and mark which components cannot be sinks, eg for edge x -> y, if x and y belong to different components then component of x cannot be a sink. Whichever components remains unmarked form sinks. Now iterate over vertices and if the vertex belongs to a sink component, print it’s number. Complexity : O(V+E)

5 Likes
3

However, the question can be done the above mentioned way, but what is wrong with the following approach http://ideone.com/iHcSIQ ? I am just making a simple adjacency matrix and checking if a[i][j]==1, then for a vertex to be a sink, a[j][i] should be 1.

1 Like
4

I did not understand, which vertex will be the sink if both a[i][j] and a[j][i] are 1? There can be a larger cycle too

5

I misunderstood the question thinking that we are talking about the vertices directly reachable from the source. Thanks anyway!!

6

@piyushkumar After finding strongly connected components, will my ans be this: for each edge (u,v), if u and v are in different SSC then u is not in the answer otherwise it is. Is it?

7

Otherwise it is only if there is no incoming edge to this component. Make a bool array for each component to see if there is an incoming or not

1 Like