Hi everyone,
I've been learning a lot of graph theory lately, and I've come across the following question, which I am having trouble with:
Suppose you are given a directed acyclic graph $$$G = (V, E)$$$ in which each vertex is colored one of two colors. You are also given two vertices $$$u$$$ and $$$v$$$ in the graph. How can I determine whether there is a path from $$$u$$$ to $$$v$$$ consisting of only one color (each intermediate vertex other than $$$u$$$ and $$$v$$$ are required to have the same color, the colors of $$$u$$$ and $$$v$$$) don't matter.
I thought about applying topological sort since it's a DAG, but then I don't really know how to proceed. Can someone please help me?
Can you share the link to the problem? I want to check if my solution is correct or not. Anyways maybe we can run dfs from the start and while calling for next calls we should also check the colors of the to node and from node?
For single query u,v u can simply use DFS keep 2 counts distance of v from u and no. Of say red nodes upto v take u as node If u wanna handle multiple queries u can use lca algorithms calc same things distance between u and v and no. Of red coloured nodes between u and v
Fix the color you want. Then just run a dfs starting from $$$u$$$ that only allows traversing vertices of that color, and see if you can ever reach $$$v$$$. There are only 2 colors, so this is $$$O(V + E)$$$.
edit: Actually, this is $$$O(V + E)$$$ regardless of the number of colors, provided that you take care to not visit all neighbors of $$$u$$$ each time.
So, if there are several queries, you can add the inputted edge between two vertices only if they are of same colour. By this way, your graph should break into several connected components and for each query, you just need to check if the two vertices 'u' and 'v' are connected to at least one common connected component in the original graph.
The graph is directed, so being in the same component doesn't necessarily mean there's a path from $$$u$$$ to $$$v$$$.
Yeah, you are right. I overlooked the directed part. Any efficient algorithm for answering queries then ?
After we break into connected components, each connected component has only one colour in it so it's the same as normal reachability problem on a DAG. I do not know of any faster method than the one in this blog.