Pagini recente » Cod sursa (job #2629336) | Cod sursa (job #631173) | Cod sursa (job #255355) | Cod sursa (job #3245255) | Cod sursa (job #1758059)
#include <fstream>
#include <vector>
using namespace std;
const char NU[] = "NU";
const char DA[] = "DA";
int find(vector<pair<int, int>>& p, int x) {
if (x == p[x].first) {
return x;
}
return (p[x].first = find(p, p[x].first));
}
void unite(vector<pair<int, int>>& p, int x, int y) {
if (p[x].second > p[y].second) {
p[y].first = x;
} else {
p[x].first = y;
}
if (p[x].second == p[y].second)
++p[y].second;
}
int main() {
vector<pair<int, int>> p;
ifstream fin("disjoint.in");
ofstream fout("disjoint.out");
int n, m;
fin >> n >> m;
p.resize(n + 1);
for (size_t iter = 0; iter < p.size(); ++iter) {
p[iter].first = iter;
p[iter].second = 1;
}
for (int iter = 0; iter < m; ++iter) {
int choice, x, y;
fin >> choice >> x >> y;
switch(choice) {
case 1:
unite(p, find(p, x), find(p, y));
break;
case 2:
fout << (find(p, x) == find(p, y) ? DA : NU) << "\n";
break;
}
}
return 0;
}