牛客小白月賽24 H--人人都是好朋友(并查集+離散化/unordered_map)

位址：​​https://ac.nowcoder.com/acm/contest/5158/H​​

解析：1e9，開不了這麼大的pr[]，是以采取離散化處理。假設輸入了 10  12 ，可以把它們存到另一個數組now[]裡：i=1,10  i=2,12，這樣就可以把數字用坐标來代替，n隻有1e6，是以pr[]開到2e6往上就可以了。使用了lower_bound來查找數字的對應位置。unordered_map也可以做，但是我的編譯器報錯，是以就沒這麼寫，先插個眼吧：

unordered_map<int,int>father;      

然後是我的離散化代碼：

#include<iostream>
#include<cstdio>
#include<map>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn=3e6;
ll pr[maxn],a[maxn],b[maxn],c[maxn];
ll tot=1;
ll now[maxn];
void init()
{
    for(int i = 1 ; i  <= tot ; i++)
    {
        pr[i]=i;
    }
}
ll find(ll  x)
{
    if(x!=pr[x])
        return pr[x]=find(pr[x]);
        return x;
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n;
        scanf("%d",&n);
        tot=1;
        for(int i = 1 ; i <= n ; i++)
        {
            scanf("%lld%lld%lld",&a[i],&b[i],&c[i]);
            now[tot++]=a[i];
            now[tot++]=b[i];
        }
        sort(now+1,now+tot+1);
        init();
        int ok = 0 ;
        for(int i = 1 ; i <= n ; i++)
        {
            ll x=lower_bound(now+1,now+tot+1,a[i])-now;
            ll y=lower_bound(now+1,now+tot+1,b[i])-now;                
            ll fa=find(x);
            ll fb=find(y);
            if(c[i]==1)
            {
                if(fa!=fb)
                    pr[fa]=fb;
            }
            else
            {
                if(fa==fb)
                {
                    ok=1;break;
                }
            }
        }
        if(!ok)
            cout<<"YES"<<endl;
        else
            cout<<"NO"<<endl;
    }
}