Pagini recente » Cod sursa (job #465190) | Cod sursa (job #2799723) | Cod sursa (job #530287) | Cod sursa (job #2592265) | Cod sursa (job #1404187)
#include <fstream>
using namespace std;
ifstream fin("disjoint.in");
ofstream fout("disjoint.out");
const int kMax = 1e5 + 5;
int n, m, TT[kMax], rnk[kMax];
int find(int x)
{
int anc;
for (anc = x; anc != TT[anc]; anc = TT[anc]);
while (x != anc)
{
int aux = TT[x];
TT[x] = anc;
x = aux;
}
return anc;
}
void unite(int x, int y)
{
x = find(x); y = find(y);
if (rnk[y] > rnk[x])
swap(x, y);
TT[y] = x;
++rnk[x];
}
int main()
{
fin >> n >> m;
for (int i = 1; i <= n; ++i)
{
TT[i] = i;
rnk[i] = 1;
}
while (m--)
{
int opt, x, y;
fin >> opt >> x >> y;
if (opt == 1)
unite(x, y);
else
fout << (find(x) == find(y) ? "DA" : "NU") << '\n';
}
return 0;
}