Cod sursa(job #3210920)
Utilizator | Cozma Diego dego | Data | 7 martie 2024 18:31:25 |
---|---|---|---|
Problema | Paduri de multimi disjuncte | Scor | 100 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva educationala | Marime | 0.98 kb |
#include <bits/stdc++.h>
using namespace std;
ifstream f("disjoint.in");
ofstream g("disjoint.out");
int t[100002], n,m,c,x,y,sz[100002];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
f>>n>>m;
for(int i=1; i<=n; i++)
{
sz[i]=1;
t[i]=i;
}
for(int i=1; i<=m; i++)
{
f>>c>>x>>y;
if(c==2)
{
while(x!=t[x])
x=t[x];
while(y!=t[y])
y=t[y];
if(t[x]==t[y])
g<<"DA\n";
else
g<<"NU\n";
}
else
{
while(x!=t[x])
x=t[x];
while(y!=t[y])
y=t[y];
if(sz[x]>sz[y])
{
t[y]=x;
sz[x]+=sz[y];
}
else
{
t[x]=y;
sz[y]+=sz[x];
}
}
}
return 0;
}