I have found a really interesting problem http://mirror.codeforces.com/problemset/problem/97/E but i am not able to solve it in the required time complexity.
The problem is that given a graph with vertices n and edges m where n,m<=1e5 and
you are also given q queries where q<=1e5 and in each query 2 vertices are given u and v.
we have to find that whether there exists a simple path with odd length between u and v in each query.
Can someone please help me in solving the problem.
Auto comment: topic has been updated by emoji (previous revision, new revision, compare).
UPD: wrong solution
That proof with bipartite argument is so beautiful that it makes my comment seem stupid! Nice :D
Actually I'm wrong. I accidentally read that path is any. My solution didn't works for case:
UPD: wrong as well, as pointed out by P_Nyagolov (thank you).
But it's not a simple path, is it?
if the path asked was not simple we could have done shortest path algorithm with states. Am i right or wrong?? It would take O(n) time though per query.
If the path did not have to be simple you can solve in O(N) precomputation and O(1) query. Read Temirulan's first version comment to see solution to this alternative problem.
If I remember correctly there is a fact that in a 2-connected-graph with odd cycle, each vertex will appear in at least one odd cycle too.
If I'm not wrong about this then partitioning the graph into 2-connected-components will solve the problem.
NOTE: I'm not sure about edge-connected or vertex-connected :)...but I think it should be vertex-connected.
This is true for vertex-connected graphs, but can you elaborate a bit on how it helps us?
If that's true then we can divide the graph into sereval bi-connected components and we can construct a tree by consider each connected component and their articulation Point as vertices. Consider the components passed by any simple path (u,v), if any of the component(vertex in new graph) on the induced path on the new graph contains a odd cycle, there is always a odd path from u to v.
Proof: consider a simple path (u', v') passing vertex u and v in original graph and they are in same bi-connected component. Destroy the path from u to v. Consider some vertex w that lies on same odd cycle as u. There are at least two paths from u and w and they differ in parity. We want to pick some w so that the cycle does not contain v, or let w=v if u and v lies on some same odd cycle. Then we pick up any simple path that does not affect the connectivity from u and w (it must exist, due to the bi-connectivity of the component and the fact that v does not lie on the odd cycle) and we can now control the parity of the (u', v') path by alternating the path from u to w.
Otherwise, the parity of any simple path from u to v does not change (because the component is bipartite) and can be computed easily. We can precompute stuff (contains odd cycle, path parity from vertex to vertex) in O(N lg N) and answer query in O(1) time.
If you pick graph G7 in this picture, the triangle is obviously biconnected, but there is no simple odd length path between the two leaf vertices.
The simple path does not pass through the triangle (aka component). It passes through one of the AP of the triangle however.