首先 N 個 unknowns 至少要有 N 條 equations
多過 N 條的話只保留 linear independent 的
之後便聯想到一個 |V| = |E| 的 Graph, 即頂環樹
有一個頂環樹, 一定是從環的部份開始解
但是不是每種環都有唯一解, 要 odd cycle 才可以 (用 determinant 可以證明)
所以每個 connected component 要至少有一個 odd cycle 才有機會有唯一解
環的解可以綫性計算, 然後順著邊計算 tree node 的解
之後多餘的 edge 只要 check 是否 consistent 便可以
總時間 O(N+M)
No comments:
Post a Comment