我梦扁舟浮震泽
雪浪摇空千顷白
其实就是图中计算两点是否连通。。。
在leetcode中碰到的图论题不算多，这次也算一个，应该也可以用并查集来做。
我们可以用提供的所有等式来建立图，然后用所有的不等式验证两点之间的连通性。
取出所有的等式建立图，其中每个顶点就是变量，变量最多26个，如果两个变量之间存在直接的相等关系，则建立无向边。
后面就是验证不等式顶点之间的连通性。。。直接dfs就好啦！
class Solution {
private:
bool dfs(char s, const char &d, vector<vector<int>> &&g, vector<bool> &vis) {
for (char next = 'a'; next <= 'z'; next++) {
if (g[s][next]) {
if (next == d)
return true;
if (!vis[next]) {
vis[next] = true;
if (dfs(next, d, std::move(g), vis))
return true;
vis[next] = false;
}
}
}
return false;
}
public:
bool equationsPossible(vector<string>& equations) {
vector<pair<char, char>> not_equals;
vector<vector<int>> g(128, vector<int>(128));
for (char it = 'a'; it <= 'z'; it++)
g[it][it] = true;
for (const string &it : equations) {
if (it[1] == '=') {
g[it[0]][it[3]] = true;
g[it[3]][it[0]] = true;
} else {
not_equals.emplace_back(it[0], it[3]);
}
}
vector<bool> vis(128);
for (const auto it : not_equals) {
char a = it.first, b = it.second;
vis[a] = true;
if (dfs(a, b, std::move(g), vis))
return false;
vis[a] = false;
}
return true;
}
};
