Cod sursa(job #2302655)

Utilizator BlaugranasEnal Gemaledin Blaugranas Data 14 decembrie 2018 22:47:15
Problema Paduri de multimi disjuncte Scor 100
Compilator c-64 Status done
Runda Arhiva educationala Marime 0.61 kb
#include<stdio.h>
int n,m,y,z,i,p[100001],r[100001],x,c,d;
int F(int i) { return p[i]==i?i:p[F(p[i])]; }
int main() {
    freopen("disjoint.in","r",stdin),freopen("disjoint.out","w",stdout),scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++)
        p[i]=i;
    while(m--) {
        scanf("%d%d%d",&x,&y,&z);
        if(x==1) {
            c=F(y),d=F(z);
            if(r[c]>r[d])
                p[d]=c;
            else if(c!=d) {
                p[c]=d;
                if(r[c]==r[d])
                    r[d]++;
            }
        }
        else
            printf("%s\n",F(y)==F(z)?"DA":"NU");
    }
}