A question about DAGs.

5 лет назад, # ^ |

← Rev. 2 →

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

→ Ответить

Peregrine_Falcon

5 лет назад, # |

← Rev. 2 →

-6

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

→ Ответить

5 лет назад, # ^ |

How?

→ Ответить

Peregrine_Falcon

5 лет назад, # ^ |

← Rev. 2 →

+13

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.

→ Ответить

5 лет назад, # ^ |

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.

→ Ответить

Peregrine_Falcon

5 лет назад, # ^ |

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

→ Ответить

5 лет назад, # ^ |

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 - Case of Computer Network can be solved by a combination of SCC and this problem.

→ Ответить

5 лет назад, # ^ |

+12

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

→ Ответить

5 лет назад, # ^ |

← Rev. 4 →

+11

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.

→ Ответить

5 лет назад, # |

+19

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.

→ Ответить

5 лет назад, # ^ |

consider that time limit is 64 MB.

→ Ответить

5 лет назад, # ^ |

So it's a problem from a specific OJ?

Heuristics.

→ Ответить

5 лет назад, # ^ |

No; But I'm using it to solve 555E - Case of Computer Network; and the time limit is 256 MB; but the constraints is 2e5 not 1e5; so I devided the time limit by 4.

→ Ответить

5 лет назад, # ^ |

These aren't queries!

→ Ответить

5 лет назад, # ^ |

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

→ Ответить

5 лет назад, # ^ |

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.

→ Ответить

Lets__go

5 лет назад, # ^ |

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

→ Ответить

5 лет назад, # ^ |

Heuristics.

→ Ответить

riadwaw

5 лет назад, # ^ |

← Rev. 3 →

+18

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

→ Ответить

brandonzhang

5 лет назад, # |

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

→ Ответить

stefanbalaz2

5 лет назад, # ^ |

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

→ Ответить

ricardogg

5 лет назад, # |

← Rev. 2 →

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)$$$.

→ Ответить