NC17881 程序自动分析题解

题目链接：https://ac.nowcoder.com/acm/problem/17881
首先看到这道题第一反应这不就是一道最基本的并查集的题目吗，但是当看到数据的时候，我们会发现i,j太大了，普通数组存不下，那该怎么办，很多人都说离散化（然而我太菜了不会），此处我的第一想法是用map来代替数组，然而map的话速度是一言难尽的，很有可能TLE,但是我还是找到了一种稳AC的代码（有兴趣的人可以看一下我的提交记录就知道了）。
前方高能： 但是如果我们将其中的map换为unordered_map时，这道题就不攻自破了，而且速度飞快 ，废话不多说上代码：

#include<iostream>
#include<algorithm>
#include<fstream>
#include<vector>
#include<unordered_map>
using namespace std;
vector<pair<int,int>> v;
unordered_map<int,int> m;//并查集的数组
inline int read(){
    int x = 0, f = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9'){
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9'){
        x = (x<<1) + (x<<3) + (ch^48);
        ch = getchar();
    }
    return x * f;
}//快读
int find(int x){
    return m[x]==x ? x : m[x]=find(m[x]);
}//并查集的查找
void merge(int x,int y){
    m[find(x)]=find(y);
}//并查集的合并
int main(){
    int t=read();
    while(t--){
        m.clear();
        v.clear();
        int flag=1;
        int n=read();
        int a,b,c;
        for(int i=1;i<=n;i++){
            a=read();
            b=read();
            c=read();
            if(!m[a]){
                m[a]=a;
            }//当输入的i从未被读入过
            if(!m[b]){
                m[b]=b;
            }//当输入的j从未被读入过
            if(c==1){
                merge(a,b);
            }
            if(c==0){
                v.emplace_back(make_pair(a,b));
            }//将需要判断的存入一个向量v中
        }
        for(auto it : v){
            if(find(it.first)==find(it.second)){
                flag=0;
                break;
            }
        }
        if(flag){
           printf("YES\n");
        }
        else
        {
           printf("NO\n");
        }
    }
    getchar();
    return 0;
}

切记unordered_map的效率极高