1.并查集基础
题目描述
现在有一个并查集，你需要完成合并和查询操作。
输入
第一行包含两个整数 N,M ,表示共有 N 个元素和 M 个操作。
接下来M 行，每行包含三个整数 Zi,Xi,Yi 。
当 Zi=1 时，将 Xi 与 Yi 所在的集合合并。
当Zi=2 时，输出Xi 与 Yi 是否在同一集合内，是的输出 Y ；否则输出 N 。
输出
对于每一个Zi=2 的操作，都有一行输出，每行包含一个大写字母，为 Y 或者 N 。
样例输入
4 7
2 1 2
1 1 2
2 1 2
1 3 4
2 1 4
1 2 3
2 1 4
样例输出
N
Y
N
Y
题解
#include <iostream> using namespace std; int main() { int n, t; cin >> n >> t; int* arr = new int[n+10]; for (int i = 0; i < n+1; i++) { arr[i] = i; } while (t--) { int a, b, c; cin >> a >> b >> c; if (a == 1) { while (arr[b]!=b) { b = arr[b]; } while (arr[c] != c){ c = arr[c]; } arr[c] = b; } else if (a == 2) { while (arr[b] != b) { b = arr[b]; } while (arr[c] != c) { c = arr[c]; } if (arr[b] == arr[c]) { cout << "Y" << endl; } else { cout << "N" << endl; } } } }
2. 红娘
题目描述
小明在A公司工作，小红在B公司工作。A公司有N名男员工，其中有P对有朋友关系。B公司有M名女员工，其中有Q对有朋友关系。假设朋友的朋友还是朋友。
每对朋友关系用两个整数(Xi, Yi)组成，表示朋友的编号分别为Xi，Yi。男人的编号是正数，女人的编号是负数。小明的编号是1，小红的编号是-1.
小明和小红是情侣，他们想撮合A、B公司的员工成为情侣。只有异性男女才能成为情侣，而且任何一方都不能脚踏两只船哦。那么，请问两公司之间，通过小明和小红认识的人最多一共能配成多少对情侣。（包括他们自己）
输入
第1行，4个空格隔开的正整数N,M,P,Q。
之后P行，每行两个正整数， Xi, Yi。
之后Q行，每行两个负整数， Xi, Yi。
输出
一个正整数，表示通过小明和小红认识的人最多一共能配成多少对情侣。（包括他们自己）
样例输入
4 3 4 2
1 1
1 2
2 3
1 3
-1 -2
-3 -3
样例输出
2
题解
#include <algorithm> #include <iostream> using namespace std; class UnionSet { private: int *roots; int length; public: UnionSet(int n) { roots = new int[n + 1]; for (int i = 1; i <= n; i++) { roots[i] = i; } length = n; } ~UnionSet() { delete[] roots; } int find(int a) { int p = a; while (roots[p] != p) { p = roots[p]; } return p; } void unionMerge(int a, int b) { int x = find(a); int y = find(b); roots[y] = x; } int countRoot() { int x = find(1); int num = 0; for (int i = 1; i <= length; i++) { if (x == find(i)) { num++; } } return num; } }; int main() { int n, m, p, q; cin >> n >> m >> p >> q; UnionSet male(n); UnionSet female(n); while (p--) { int x, y; cin >> x >> y; male.unionMerge(x, y); } while (q--) { int x, y; cin >> x >> y; female.unionMerge(-x, -y); } cout << min(male.countRoot(), female.countRoot()) << endl; return 0; }
3.滑雪
题目描述
David是个滑雪初学者，他还没有学会如何在滑行过程中控制方向，也不知道如何停下来。所以他的滑行方式只能是在一个高高的雪堆上调整好向北，东，南或西移动的方向，然后直线滑下来，一直滑倒另一个雪堆底下才能停下来。
他发觉以这种方式，有些雪堆他是无法到达的。因此，他现在想在已有的雪堆基础上，自己再人为地增加一些雪堆，使得他可以从任何雪堆转移到其他任何雪堆。他请求您帮他找到需要创建的雪堆的最少数量。
我们假设David只能在整数坐标处堆积雪堆。
输入
输入的第一行包含一个整数n（1≤n≤100），表示已有的雪堆数量。 接下来的n行中的每行包含两个整数Xi和Yi（1≤Xi，Yi≤1000），表示已有的第i个雪堆的坐标。
请注意，北方向与Oy轴方向一致，因此东方向与Ox轴方向一致。 所有雪堆的位置都不同。
输出
输出为使David能够从任何雪堆到达其他任何雪堆而需要创建的最小雪堆数。
样例输入
2
2 1
1 2
样例输出
1
题解
#include <algorithm> #include <iostream> #include <set> using namespace std; class UnionSet { private: int *roots; int length; public: UnionSet(int n) { roots = new int[n + 1]; for (int i = 1; i <= n; i++) { roots[i] = i; } length = n; } ~UnionSet() { delete[] roots; } int find(int a) { if(roots[a] == a) { return a; }else { return find(roots[a]); } } void merge(int a, int b) { int x = find(a); int y = find(b); if (x != y) { roots[y] = x; } } int count() { set<int> s; for (int k = 1; k <= length; k++) { s.insert(roots[k]); } return s.size(); } }; struct Point { int x; int y; }; int main() { int n; cin >> n; UnionSet us(n); Point *point = new Point[n + 1]; for (int i = 1; i <= n; i++) { cin >> point[i].x >> point[i].y; } for (int i = 1; i < n; i++) { for (int j = i + 1; j <= n; j++) { if (point[i].x == point[j].x || point[i].y == point[j].y) { us.merge(i, j); } } } cout << us.count() - 1 << endl; return 0; }
