I was able to solve it just by computing matrix determinant. Nothing to do with graphs, just taking advantage of matrix sparsity.