解决方案
方法一:联通分量
思路
所有相互等于的变量能组成一个联通分量。举一个例子,如果 a=b, b=c, c=d
,那么 a, b, c, d
就在同一个联通分量中,因为它们必须相等。
算法
第一步,我们基于给定的等式,用深度优先遍历将每一个变量按照联通分量染色。
将联通分量染色之后,我们分析形如 a != b
的不等式。如果两个分量有相同的颜色,那么它们一定相等,因此如果说它们不相等的话,就一定无法满足给定的方程组。
否则,我们的染色就可以看作是一组能满足方程组约束的方案,所以结果是 true。
复杂度分析
-
时间复杂度: ,其中 是方程组
equations
的数量。 -
空间复杂度: ,认为字母表的大小是 的。