-
Notifications
You must be signed in to change notification settings - Fork 3
/
990.cpp
49 lines (49 loc) · 1.28 KB
/
990.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
class DisjointSet {
private:
vector<int> parent;
vector<int> rank;
public:
DisjointSet(int size) {
parent.resize(size, 0);
rank.resize(size, 0);
for (int i = 0; i < size; ++i) parent[i] = i;
}
int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]);
}
return parent[x];
}
void join(int x, int y) {
int pX = find(x);
int pY = find(y);
if (pX == pY) return;
if (rank[pX] > rank[pY]) {
parent[pY] = pX;
}
else if (rank[pX] < rank[pY]) {
parent[pX] = pY;
}
else {
parent[pY] = pX;
rank[pX]++;
}
}
};
class Solution {
public:
bool equationsPossible(vector<string>& equations) {
DisjointSet* disjointSet = new DisjointSet(26);
for (auto& equation : equations) {
if (equation[1] == '=') disjointSet->join(equation[0] - 'a', equation[3] - 'a');
}
for (auto& equation : equations) {
if (equation[1] == '!') {
int pA = disjointSet->find(equation[0] - 'a');
int pB = disjointSet->find(equation[3] - 'a');
if (pA == pB) return false;
}
}
return true;
}
};