Cod sursa(job #3371496)

Utilizator Moriiandrei Morii Data 30 octombrie 2026 16:34:20
Problema Paduri de multimi disjuncte Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.13 kb
#include <bits/stdc++.h>
#define int long long
using namespace std;


int n,m;
struct elem{

  int st,dr,cost;


}x[400001];
int t[200001],r[200001];
bool comp(elem a,elem b)
{
      return a.cost < b.cost;
}

int find(int nod)
  {
      if(nod == t[nod])
        return nod;
      else return t[nod] = find(t[nod]);

  }
//int t[200001],r[200001];

void unire(int a,int b)
    {
        int p1 = find(a),p2 = find(b);
        if(r[p1] > r[p2])
           {
               t[p2] = p1;
               r[p1]++;

           }
        else{


              t[p1] = p2;
               r[p2]++;


        }

    }
  vector<pair<int,int>>xx;



signed main()
{
    freopen ("disjoint.in","r",stdin);
    freopen ("disjoint.out","w",stdout);
   cin >> n >> m;
   for(int i = 1;i<=n;++i)
    t[i] = i,r[i] = 1;

  while(m--)
    {
        int t,x,y;
        cin>> t >> x >> y;
        if(t == 1)
        {
            unire(x,y);

        }
        else{
             if(find(x) == find(y))
                cout << "DA\n";
                else cout << "NU\n";

        }
    }







}