I_love_PMK's blog

How to solve this hard problem about DAG.
By I_love_PMK, 10 years ago, In English

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 :

  1. X is acessable to Y

  2. 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.

  • Vote: I like it
  • +10
  • Vote: I do not like it

»
10 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

edit: I've misread the problem statement

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Directed graph doesn't mean DAG.

→ Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it +9 Vote: I do not like it

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.

→ Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      You haven't removed the 1->3 edge.

      → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        oh thank you.

        → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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 ?

        → Reply
        • »
          »
          »
          »
          »
          10 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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.

          → Reply
        • »
          »
          »
          »
          »
          10 years ago, # ^ |
            Vote: I like it -25 Vote: I do not like it

          RIP a Hoà

          → Reply
»
10 years ago, # |
  Vote: I like it +5 Vote: I do not like it

We can transform this problem to this problem.

→ Reply