Find odd length path between two nodes in undirected graph (multiple queries)

Revision en6, by pabloskimg, 2017-10-23 06:40:22

I'm trying to solve the following problem (Electrical Pollution): (please read the problem statement). So basically we are given many 2 variable (x + y = c) and 1 variable (x = c) linear equations, i.e measurements, and then we are given multiple 2 variable (w + z = ?) and 1 variable (w = ?) queries and we have to either give the exact result if the answer can be inferred from the previous measurements, or * otherwise.

My idea is to build a graph where the nodes are the variables and the edges are the 2-variable equations connecting them.

1) As a first step, we already know the values of the variables in the 1-variable measurements, and starting from them we can propagate and infer the values of all the other variables connected with BFS over the graph.

2) As a second step, we can solve equation systems with an odd number of equations where there are the same number of equations and variables. Basically we can run DFS, find loops (backward edges), if the loop has an odd length then we can easily solve the equation system of the edges in that loop (say, we solve for the first variable in the loop) and then we propagate to the whole connected component with BFS (as in 1).

3) It turns out that 1) and 2) are not enough, because it's not necessary to know the exact values of both variables to be able to know the value of their sum. In fact, given a 2-variable query (x + y = ?), if we can find a path (not necessarily a loop) of odd length, and if we enumerate the measurements along that path with 1, 2, 3, ..., n, then we can solve the equation (x + y = ?) by adding the measurements with odd index and subtracting the measurements with even index along that path. Moreover, any odd-length path would do the trick, because the final result will be the sum of the variables at both ends of the path, and variables in between just cancel each other (like a sort of telescoping sum

My question is basically about how to implement point 3). Right know I'm not sure about how to do it. I guess it shouldn't be necessary to find a specific path, because the final result will not depend on the exact path taken, just on the end points. Maybe precomputing partial sums and combining them using LCA somehow or something like that could work, but I cannot see how to exactly do the combination.

Any help will be deeply appreciated :)

Thanks in advance

Tags graph, dfs, bfs, path query


  Rev. Lang. By When Δ Comment
en6 English pabloskimg 2017-10-23 06:40:22 66
en5 English pabloskimg 2017-10-23 06:35:31 407
en4 English pabloskimg 2017-10-23 02:25:23 69
en3 English pabloskimg 2017-10-21 19:12:04 4 Tiny change: 'pagate to whole con' -> 'pagate to the whole con'
en2 English pabloskimg 2017-10-21 19:07:20 1
en1 English pabloskimg 2017-10-21 19:05:43 2279 Initial revision (published)