P1955 [NOI2015] 程序自动分析

https://www.luogu.com.cn/problem/P1955.

离散化+并查集

这道题是一个并查集的经典题目，因为这个题目的数据太大，我们无法直接用f[i]=i来初始化所有的结点，但是输入的数量只有n，可以先进行离散化再进行根节点的初始化。

这道题的离散化不需要保持数据的保序性，所以我们可以借助哈希来离散化，也就是STL中的unordered_map来进行离散化。

如果需要保持有序性我们需要进行1.去重（可以用到unique去重函数）2.排序3.二分索引（可以用到lower_bound函数）

#include<iostream>
#include<cmath>
#include<vector>
#include<map>
#include<stack>
#include<queue>
#include<cstring>
#include<algorithm>
#include<iomanip>
#include<vector>
#include<list>
#include<unordered_map>
#include<limits>
#define mem(a,n) memset(a,n,sizeof a)
#define endl '\n'
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define SYS system("pause");
#define For(i, n) for (int i = 0; i< n;i++)
#define FOR(i, n) for (int i = 1; i <= n;i++)
#define rFor(i, n) for (int i = n; i > 0;i--)
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
ll gcd(ll a,ll b){ll d; while(b){ d=b; b=a%b; a=d; } return a;}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
ll qpow(ll x, ll y) { ll ans = 1; for (; y > 0; y >>= 1) { if (y & 1)ans *= x; x *= x; } return ans;}
ll qpow(ll x, ll y, int MOD) { ll ans = 1; for (; y > 0; y >>= 1) { if (y & 1)ans = ans*x%MOD; x = x*x%MOD; } return ans;}
void exgcd(int a,int b,int &x,int &y){ if(b==0){ x=1;y=0;return; } exgcd(b,a%b,x,y); int temp=y; y=x-(a/b)*y, x=temp; return;}
int downcheck(int l, int r){ while (l < r){ int mid = l + r >> 1; if ("check(mid)") r = mid; else l = mid + 1; } return l;}
int upcheck(int l, int r){ while (l < r){ int mid = l + r + 1 >> 1; if ("check(mid)") l = mid; else r = mid - 1;} return l;}
int doublecheck(int l,int r){ while(r-l>1e-8){ int mid=(l+r)>>1; if("check(mid)") l=mid; else r=mid;} return l; }
#define int long long
const int N = 1e6+10,M=20;
const int inf=0x3f3f3f3f;
const int mod=1e9+7; 
const double pi = acos(-1.0);
int n,t,m;
int f[N];
int cnt = 0;
unordered_map<int, int> mp;      //进行离散化记录的哈希表
int x1[N], x2[N], vis[N];
int find(int x){
    if(f[x]==x)
        return x;
    return f[x] = find(f[x]);
}
void join(int x,int y){
    int fx = find(x), fy = find(y);
    if(fx!=fy)   f[fx] = fy;
}
int merge(int x){    //离散化
      if(mp.count(x)==0) mp[x] = ++cnt;   
      return mp[x];
}
signed main(){{}
    //IOS
    cin >> t;
    while(t--){
        mp.clear();
        cnt = 0;
        int y1, y2;
        cin >> n;
        FOR(i, 2*n)    f[i] = i;   //注意初始化结点数为2n，因为可能最多的数为2n
        FOR(i, n){
            cin >> y1 >> y2 >> vis[i];
            x1[i] = merge(y1);
            x2[i] = merge(y2);    //存入离散化后的值
        }
        FOR(i,n){
            if(vis[i]==1){
                join(x1[i], x2[i]);      //判断相等就是直接合并集合
            }
        }
        bool flag = 1;
        FOR(i,n){
            if(vis[i]==0){               //判断不等就是看看是否在同个集合
                if(find(x1[i])==find(x2[i])){
                    flag = 0;
                    break;
                }
            }
        }
        if(flag)
            cout << "YES" << endl;
        else
            cout << "NO" << endl;
    }
    SYS
    return 0;
}