smhh22's blog

A question about DAGs.
By smhh22, history, 5 years ago, In English

Hi;

can you help me with this problem?:

We have DAG with n vertices and m edges. We have q queries, each query has two integers v[i] and u[i], determine for each query that if there is a path starting at v[i] and finishing at u[i].

n, m, q <= 1e5

thanks, and sorry for my bad English. (:

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

Comments Comments (28)
| Write comment?
»
5 years ago, # |
← Rev. 2   Vote: I like it -28 Vote: I do not like it

[Deleted]

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

    Pay attention to the constraints. You're not able to do dfs for each query.

    → Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it -6 Vote: I do not like it

Seems like top sort. You can use the half idea of SCC. Problem link please?

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

    How?

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
      ← Rev. 2   Vote: I like it +13 Vote: I do not like it
      • Use integer visited array.
      • In the first DFS push all the nodes in a stack.
      • Now, it's time for the second DFS. Using the stack. For each DFS we'll have different visited marker.
      • In this traversal, if we encounter any visited node, we'll make the current nodes visited marker as the same as encountered node. We'll do that in time of return.
      • For each query, if the source and target have the same visited marker. Then there is a path.

      This idea for the blog post's problem seems right to me. Help me if I'm wrong. I couldn't find any problem like that. Give me if you have any. The link you gave, have 2800 complexity. So, it's better for me now to stay away. Maybe later. Thank You.

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

        I don't really understand your algorithm, but I think this can't possibly be correct. Look at this simple DAG:

        (1) ---> (2)

        If I understood correctly, then you claim there's a path from $$$u$$$ to $$$v$$$ if and only if $$$u$$$ and $$$v$$$ have the same visited marker. Because there is a path from 1 to 2 they must have the same marker. But then there must be a path from 2 to 1 because they have the same marker, which isn't true.

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

          Sorry, my algorithm broke in the following graph. 1 -> 2 2 -> 3 2 -> 4 5 -> 4 It was a mistake.

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

    So what to do after top sort?

    There is no guarantee that if u is after v in a top sort, so there is a path from v to u.

    It seems that 555E - Дело о компьютерной сети can be solved by a combination of SCC and this problem.

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

      I think I'm an idiot today, I can't see the connection between 555E and your problem either.

      If you're interested here's how I would do 555E:

      Spoiler
      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
        ← Rev. 4   Vote: I like it +11 Vote: I do not like it

        If I correctly understood the problem statement my solution is this:

        Spoiler

        Sorry for my bad English. If some sentences of my solution is not obvious for you, ask for proof.

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

There's a well-known approach for finding all such pairs using bitsets. Let's say that the vertices are numbered $$$0$$$ through $$$N-1$$$ in reverse topological order and for each vertex $$$v$$$, there's a bitset with $$$v$$$ bits where the $$$u$$$-th bit is 1 if there's a path from $$$v$$$ to $$$u$$$. For each edge $$$v \rightarrow u$$$, you just OR the bitset for $$$v$$$ with the bitset for $$$u$$$ and make sure the $$$u$$$-th bit is also $$$1$$$ (since that wasn't in the bitset).

This takes $$$N^2/2$$$ bits of memory, which is approx. 600 MB, and at most $$$NM/64$$$ bitwise operations (on a 64-bit machine), which is approx. 150 million, with no extra cache misses. Not that much.

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

    consider that time limit is 64 MB.

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

      So it's a problem from a specific OJ?

      Heuristics.

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

        No; But I'm using it to solve 555E - Дело о компьютерной сети; and the time limit is 256 MB; but the constraints is 2e5 not 1e5; so I devided the time limit by 4.

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

          These aren't queries!

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

            Look at this comment: https://codeforces.net/blog/entry/69481?#comment-539810

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

              It's possible to transform a problem into a more general one that isn't solvable under the constraints of the original problem — it happened to me many times. Your solution to the original problem can be correct (or wrong) and it wouldn't affect the constraints you demand for this specific version.

              In this case, riadwaw's suggestion below works, so even this version is solvable with low memory. I'd choose a higher block size than 64 though (as large as possible) to keep cache efficiency and possible compiler optimisations through loop unrolling and SIMD.

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

    Is there a better solution than O(NM/64) time complexity within 1024MB of Memory

    → Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 3   Vote: I like it +18 Vote: I do not like it

    Let's solve it for all destinations 0..63 in O(M) and O(n) memory, remember all results, then clear the memory and solve for all destinations 64..127 etc

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

I think it should be possible to process all queries offline using the smaller-to-larger optimization.

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

    there is no possible way of managing that because its a dag and a node can have more than 1 parent

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

I got one idea, however I'm not sure if it will work, maybe some of the more experienced coders could check my work.

For simplicity, Let's assume that the there is just one vertex with no parents.

Let's start by picking one DFS tree of the given DAG (rooted at the node without parents). Now, we can notice that since the graph is DAG each edge in the graph will either be tree edge or edge that link current node to some other subtree. For each node we keep list of all the subtrees this node has links. It seems pretty clear that node $$$u$$$ is reachable from node $$$v$$$ if $$$u$$$ is in some subtree of $$$v$$$.

With clever implementation and using binary search we can store all the subtrees each node has links to and we can answer each query in $$$O(\log N)$$$.

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

    For simplicity, Let's assume that the there is just one vertex with no parents.

    Are you sure this is an innocent "without loss of generality..." assumption? Does your solution generalize?

    With clever implementation and using binary search we can store all the subtrees each node has links to and we can answer each query in $$$O(\log N)$$$.

    Can you explain how you plan to do this? Right now you sound a bit like "and then we solve the problem by solving the problem".

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

      It seems like the problem is when there are more roots.

      Since in total there are M edges, for each tree we build we can use euler tour to be able to store the subtrees as consecutive intervals, then for each node we store all the subtrees this node can cover, as intervals, then the query is reduced to check if one number is present at one of the intervals, and this can be checked binary search.

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

      When there are multiple vertices without parents, you can just add one dummy vertex that has edges to all of them. It doesn't affect reachability.

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

        I didn't know about this trick of adding dummy vertex, are there more cases or problems when we can add dummy vertex to simplify things?

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

    So what about memory?

    → Reply