http://www.spoj.com/problems/TPCPPLAR/
Given a directed graph G = (V,E), N vertices and M arcs. (N <= 150000, M <= 300000)
A node X called "acessable" to Y if there is a path from X to Y
A node X called "popular" if every node Y in V fulfill one of two conditions :
X is acessable to Y
Y is acessable to X
The Problem : Given graph G, count the number of popular node.
Someone has a solution for this problem.
I used Topo sorting, but I'm stucking at how to check all node previous i can go to i.
Sorry for my bad English.
edit: I've misread the problem statement
Directed graph doesn't mean DAG.
after using tarjan it become DAG
Let's first topologically sort our DAG. Later in the text comparison A < B means that vertex A stands before vertex B in topological order.
Now let's notice that for vertex V an edge that connects vertices V1 < V and V2 > V doesn't influence on the fact whether V is popular. Let's remove all such edges and see whether there exists a vertex V1 < V that has zero output degree or V2 > V that has zero input degree, if so — V is not popular, otherwise it is.
To get an
or O(E) solution, you need to iterate over the vertices in topological order and maintain all the in-out degrees.
I'm wondering this test case
1 -> 2, 1 -> 3, 2 -> 4, 3 -> 4
After topo sorting it become : 1 2 3 4
In degree : 0 1 1 2
Out degree : 2 1 1 0
Let's consider V = 2, no V1 < V has zero out degree or V2 > V has zero in degree, but 2 isn't a popular vertice.
You haven't removed the 1->3 edge.
oh thank you.
If with remove edge for each vertex V separately, a vertex can be removed many time. I think that in that case it will be TLE. If we remove an edge at most one.
Example:
1->2, 1-3, 2->4, 3->4 like I_love_PMK example.
We remove 1->3 then 3 will have input degree equal to 0. After that, 1 will be not popular but actually, 1 is a popular vertex.
Could you explain more about your idea ?
It's pretty obvious that an edge (V1; V2) will be removed only for vertices V1 < V < V2. I said that we'll traverse the vertices in topological order, and this has some sense. For each edge (V1; V2) we can remove it after processing vertex V1 and add it before processing vertex V2.
Well, we'll need to maintain the number of zero-out-degree vertices to the left of V and the number of zero-in-degree vertices to the right of V, but I think it shouldn't be too hard to understand how to do that.
RIP a Hoà
We can transform this problem to this problem.
I've read that, I want to know the solution too :D