引用

并查集介绍

啰嗦

因为本题是newoj的一个比赛,所以暂时没有题目链接,后续的话管理员应该会放在oj上

题目描述

现在给定一些变量的等于或者不等于的约束,请你判断这些约束能否同时满足。
输入时变量为x1,x2,...,xn,均以x开始,x后面为该变量对应的编号。
约束条件只有"="或者"!="。

样例

输入格式

输入第一行为正整数T,表示存在T组测试数据。
每组测试数据第一行为正整数n,表示约束条件的数量。
接下来n行,每行以下列形式输出

xi = xj
xi != xj

其中i和j表示对应变量的编号。

输出格式

对于每组测试数据,输出一行Yes表示可以满足,输出No表示不能满足。

数据范围

$ T \le 10 $
$ n \leq 1000000 $
$ 1 \leq i , j \leq 10^9 $

输入样例

2
4
x1 = x7
x9 != x7
x13 = x9
x1 = x13
2
x1 = x2
x2 = x1

输出样例

No
Yes

算法

(并查集) $O(logn)$

起初并没有想到用并查集的方法,只是用数组单纯地查询,但这肯定会超时的,数据范围太大了

用了并查集后,从题目的性质可以发现用unordered_map比较好,因为不单单是存映射关系(需要离散化,所以value不是存运算符右边的数),应该把值映射为下标,考虑到数据范围的原因,不用vector是因为需要在 $ O(1) $ 的时间复杂度返回指定元素的下标,才好在并查集中判断连通问题(这题也可以转换为判断连通问题,等号为连通,只需判断不等号左右两边的数是否都是同一个父节点)

时间复杂度

优化平均时间复杂度最坏时间复杂度
无优化$O(logn)$$O(n)$
路径压缩$O(\alpha(n))$$O(logn)$
按秩合并$O(logn)$$O(logn)$
路径压缩 + 按秩合并$O(\alpha(n))$$O(\alpha(n))$

C++ 代码

#include <iostream>
#include <string>
#include <vector>
#include <unordered_map>

using namespace std;

const int N = 3e5 + 30;

typedef pair<string , string> PSS;

int p1[N]; //存储每个点的祖宗节点

int T , n , flag , idx;

string x1 , op , x2;

unordered_map<string , int> alls;
vector<PSS> e , ne; 

// 返回x的祖宗节点
int find(int x) {
    if (p1[x] != x) p1[x] = find(p1[x]);
    return p1[x];
}

int main () {
    
    cin >> T;
    
    for (int i = 0; i < T; i ++) {
        
        cin >> n;
        idx = 1;
        flag = 0;
        alls.clear();
        e.clear();
        ne.clear();
        for(int j = 0; j < n; j ++) {
            cin >> x1 >> op >> x2;
            if(op == "=") e.push_back({x1 , x2});
            else ne.push_back({x1 , x2});
            if(!alls.count(x1)) alls[x1] = idx ++;
            if(!alls.count(x2)) alls[x2] = idx ++;
        }
        
        // 初始化,假定节点编号是1~n idx最后会多加1
        for (int k = 1; k < idx; k ++ ) p1[k] = k;
        
        for(int j = 0; j < e.size(); j ++)
            p1[find(alls[e[j].first])] = find(alls[e[j].second]);
            
        
        for(int j = 0; j < ne.size(); j ++) {
            if(find(alls[ne[j].first]) == find(alls[ne[j].second])) {
                flag = 1;
                break;
            }
        }
        
        if(flag) cout << "No" << endl;
        else cout << "Yes" << endl;
    }
    
    return 0;
}

过一半数据的代码

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>

using namespace std;

const int N = 1e9 + 10;

string x1 , op , x2;

int T , n , flag;

vector<pair<string , string>> x11 , x22;

int main(){
    
    cin >> T;
    
    for(int i = 0; i < T; i ++) {
        cin >> n;
        for(int j = 0; j < n; j ++) {
            cin >> x1 >> op >> x2;
            if(op == "=") x11.push_back({x1 , x2});
            else x22.push_back({x1 , x2});
        }
        
        sort(x11.begin() , x11.end());
        sort(x22.begin() , x22.end());
        x11.erase(unique(x11.begin() , x11.end()) , x11.end());
        x22.erase(unique(x22.begin() , x22.end()) , x22.end());
        for(int k = 0; k < x11.size(); k ++) {
            for(int l = 0; l < x22.size(); l ++) {
                if(x11[k].first == x22[l].first || x11[k].first == x22[l].second ||
                    x11[k].second == x22[l].first || x11[k].second == x22[l].second) {
                    flag = 1;
                    break;
                }
            }
            if(flag) break;
        }
        
        if(flag) cout << "No" << endl;
        else cout << "Yes" << endl;
        
        flag = 0;
        x11.clear();
        x22.clear();
    }
    
    return 0;
}

Q.E.D.


都懂一点,不是很懂的小捞仔