I'm trying to solve the following problem (Electical Pollution): https://www.urionlinejudge.com.br/judge/en/problems/view/1334 (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 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.
My question is basically how to implement point 3). Right know I have no clue about how to do it. I'm guessing that probably it's not necessary to find a specific path, because as long as the path has odd length the final result does not depend of the exact path taken.
