洛谷 AC，UOJ 97：（没过 Extra Tests 倒扣 3 分）

#include<bits/stdc++.h>
using namespace std;
#warning "by S__B"

const int MAXN=200010;

struct ask{
    int x,y,e;
    bool operator<(const ask &Node){
        return e>Node.e;
    }
}data[MAXN];

class Dsu{
    private:
        int fa[MAXN];
    public:
        inline void init(const int &LEN){
            for(int i=1;i<=LEN;++i)
                fa[i]=i;
        }    
        inline int get(const int &x){
            if(fa[x]==x)
                return x;
            return fa[x]=get(fa[x]);    
        }
        inline bool same_root(const int &x,const int &y){
            return get(x)==get(y);
        }
        inline void merge(const int &x,const int &y){
            if(!same_root(x,y))
                fa[get(y)]=get(x);
        }
};

int n,t;

int main(){
    cin>>t;
    while(t--){
        bool f=1;
        Dsu dsu;
        memset(data,0,sizeof(data));
        vector<int>v;
        cin>>n;
        for(int i=1;i<=n;++i){
            cin>>data[i].x>>data[i].y>>data[i].e;
            v.push_back(data[i].x);
            v.push_back(data[i].y);
        }
        sort(v.begin(),v.end());
        v.erase(unique(v.begin(),v.end()),v.end());
        for(int i=1;i<=n;++i){
            data[i].x=lower_bound(v.begin(),v.end(),data[i].x)-v.begin();
            data[i].y=lower_bound(v.begin(),v.end(),data[i].y)-v.begin();
        }
        dsu.init(v.end()-v.begin());
        sort(data+1,data+1+n);
        for(int i=1;i<=n;++i){
            if(data[i].e)
                dsu.merge(data[i].x,data[i].y);
            else if(dsu.same_root(data[i].x,data[i].y)){
                f=0;
                break;
            }   
        }
        if(f)puts("YES");
        else puts("NO");
    }
}

洛谷 90，UOJ 90：

#include<bits/stdc++.h>
using namespace std;
#warning "by S__B"

const int MAXN=1000010;

struct ask{
    int x,y,e;
    bool operator>(const ask &Node){
        return e>Node.e;
    }
}data[MAXN];
int v[MAXN];

class Dsu{
    private:
        int fa[MAXN];
    public:
        inline void init(const int &LEN){
            for(int i=1;i<=LEN;++i)
                fa[i]=i;
        }    
        inline int get(const int &x){
            if(fa[x]==x)
                return x;
            return fa[x]=get(fa[x]);    
        }
        inline bool same_root(const int &x,const int &y){
            return get(x)==get(y);
        }
        inline void merge(const int &x,const int &y){
            if(!same_root(x,y))
                fa[get(y)]=get(x);
        }
};

int n,t;

int main(){
    cin>>t;
    while(t--){
        int cur=1;
        bool f=1;
        Dsu dsu;
        memset(data,0,sizeof(data));
	    memset(v,0,sizeof(v));
        cin>>n;
        for(int i=1;i<=n;++i){
            cin>>data[i].x>>data[i].y>>data[i].e;
            v[cur++]=data[i].x;
            v[cur++]=data[i].y;
        }
        sort(v+1,v+1+cur);
        int now=unique(v+1,v+1+cur)-v;
        for(int i=1;i<=n;++i){
            data[i].x=lower_bound(v+1,v+1+now,data[i].x)-v;
            data[i].y=lower_bound(v+1,v+1+now,data[i].y)-v;
        }
        dsu.init(now);
		sort(data+1,data+1+n,[](ask a,ask b)->bool{return a>b;});
        for(int i=1;i<=n;++i){
            if(data[i].e)
                dsu.merge(data[i].x,data[i].y);
            else if(dsu.same_root(data[i].x,data[i].y)){
                puts("NO");
				f=0;
                break;
            }   
        }
        if(f)puts("YES");
    }
}

参考思路大体相近的 UOJ 神犇洛谷 AC，UOJ AC 代码

#include <bits/stdc++.h>
using namespace std;
#warning "UOJ某神犇源码"
int f[1000001], b[3000001], t, n, flag, pos;
struct node
{
  int x, y, op;
} a[1000001];
void init(int n)
{
  for (int i = 1; i <= n; i++)
    f[i] = i;
}
int cmp(node a, node b)
{
  return a.op > b.op;
}
int find(int x)
{
  return f[x] == x ? x : f[x] = find(f[x]);
}
void merge(int a, int b)
{
  f[find(b)] = find(a);
}
int readnum()
{
  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 main()
{
  t = readnum();
  while (t--)
  {
    memset(a, 0, sizeof a), memset(b, 0, sizeof b), memset(f, 0, sizeof f);
    pos = 1, flag = 0;
    n = readnum();
    for (int i = 1; i <= n; i++)
    {
      a[i].x = readnum(), a[i].y = readnum(), a[i].op = readnum();
      b[pos++] = a[i].x, b[pos++] = a[i].y;
    }
    sort(b + 1, b + pos + 1);
    int now = unique(b + 1, b + pos + 1) - b;
    for (int i = 1; i <= n; i++)
      a[i].x = lower_bound(b + 1, b + now + 1, a[i].x) - b, a[i].y = lower_bound(b + 1, b + now + 1, a[i].y) - b;
    init(now);
    sort(a + 1, a + n + 1, cmp);
    for (int i = 1; i <= n; i++)
    {
      if (a[i].op == 1)
        merge(a[i].x, a[i].y);
      else if (find(a[i].x) == find(a[i].y))
      {
        puts("NO"), flag = 1;
        break;
      }
    }
    if (!flag)
      puts("YES");
  }
  return 0;
}