Code & Func

第51天，考完期末了，hhh。虽然还有一门恶心的Survey没写。

今天的题目是Satisfiability of Equality Equations:

一道并查集的题目，先遍历一次==的式子，建立并查集，然后再遍历一次!=的式子，判断!=两边的字符是否属于不同的两个集合即可。

1
bool equationsPossible(vector<string>& equations) {
2
    vector<int> imap(26);
3
    for(int i = 0;i < 26; i++) imap[i] = i;
4
    for(auto &e: equations) {
5
        if (e[1] == '!') continue;
6
        int i1 = e[0] - 'a', i2 = e[3] - 'a';
7
        while(imap[i1] != i1) i1 = imap[i1];
8
        while(imap[i2] != i2) i2 = imap[i2];
9
        imap[i1] = i2;
10
    }
11

12
    for(auto &e: equations) {
13
        if (e[1] == '=') continue;
14
        int i1 = e[0] - 'a', i2 = e[3] - 'a';
15
        while(imap[i1] != i1) i1 = imap[i1];
8 collapsed lines
16
        while(imap[i2] != i2) i2 = imap[i2];
17
        if (i1 == i2) {
18
            return false;
19
        }
20
    }
21

22
    return true;
23
}