特斯拉店面

可以用topological sort，先做graph (right variable -> left variable)，再做每个variable的indegree，加variable入queue当它indegree为零

chienlung 发表于 2022-3-24 19:34
可以用topological sort，先做graph (right variable -> left variable)，再做每个variable的indegree，加v ...

谢谢！我大概明白了！

LC 770 ? 楼主有没有代码 展开讲一下

应该可以借鉴 topology sort 的思想，通过 equation 来建立 dependency，然后在 topology sort 的过程中来逐渐 materialize 每一个变量的 value，如果最后发现 topology sort 结束了之后仍然有 variable 没有被 materialize，那么说明有向图中有环，也就是无解的情况

有点不理解Topological sort的方法怎么解决有环的问题呀，比如

1. ['a=b+3', 'b=c+2', 'c=a+b']

复制代码

dependency graphic是有环的，但是方程是有解的：a=-2,b=-5,c=-7

不知道直接读成矩阵然后求解Ax=b给不给过，det(A) == 0 才是无解。虽然面试现场手撸高斯消元不太来得及，但应该是正规的解法吧？

不纯洁的锌 发表于 2023-1-16 12:06
有点不理解Topological sort的方法怎么解决有环的问题呀，比如dependency graphic是有环的，但是方程是有解 ...

存indegreeMap
你这例子
a -> 1
b -> 1
c -> 2

没有为0入度的，肯定无解 topo 的时候的Queue一开始就empty

别的例子的话
a = b + 1    b = a + 1   c = 1
或
a = b + c.     d = a + 1   b = d + c      c = 1

不然就是遍历的时候 存路径，不然就是最后的时候check 结果数 是不是等于变量数