L2-010 排座位 (25 分) c++ 并查集

分析

二维数组表示，会有测试点过不去

1. 二维数组去表示他们的关系，在判断：x和y这两个人时，如果他们之间有敌对，然而也有共同的朋友，这个地方的时候，我们可以去找所有和x、y两个点有关系的人，通过一层循环，当某个人j同时满足和x存在盆友关系，满足条件；
2. 第二个测试点过不去，因为会出现，朋友的朋友也是朋友，所以这样写有bug，所以可以考虑并查集；

#include <bits/stdc++.h>
using namespace std;int a[105][105];int main() {int n, m, k;cin >> n >> m >> k;for (int i = 1; i <= m; i++) {int x, y, val;cin >> x >> y >> val;a[x][y] = val;a[y][x] = val;}for (int i = 1; i <= k; i++) {int x, y;cin >> x >> y;if (a[x][y] == 1)cout << "No problem" << endl;if (a[x][y] == 0)cout << "OK" << endl;int f = 0;if (a[x][y] == -1) { //找所有和x组队为1的，和y组队为1的是否有同一个人for (int j = 1; j <= n; j++) {if (a[x][j] == 1 && a[y][j] == 1) {cout << "OK but..." << endl;f = 1;}}if (f == 0)cout << "No way" << endl;}}return 0;
}

并查集

1. 并查集使用参考：https://blog.csdn.net/weixin_51995229/article/details/124313167?spm=1001.2014.3001.5502
2. 也用一个二维数组，敌对和朋友能直接根据二维数组的值进行判断；x和y这两个人时，如果他们之间有敌对，然而也有共同的朋友，这个的判断，我们可以利用并查集，去找他们的公共祖先是否相同；
3. 将存在朋友的关系的合并在一块，做一个并查集，然后敌对关系的直接在数组中表示就行；

#include <bits/stdc++.h>
using namespace std;int a[105][105];
int f[105];
void init(int n) {for (int i = 1; i <= n; i++)f[i] = i;
}
int find(int x) {if (f[x] == x)return x;return f[x] = find(f[x]);
}
void unit(int x, int y) {int a = find(x);int b = find(y);f[b] = f[a];
}
int main() {int n, m, k;cin >> n >> m >> k;init(n);for (int i = 1; i <= m; i++) {int x, y, val;cin >> x >> y >> val;a[x][y] = val;a[y][x] = val;//将朋友的关系建立起来if (val == 1) {unit(x, y);}}while (k--) {int x, y;cin >> x >> y;if (a[x][y] == 1)cout << "No problem\n";else if (a[x][y] == 0)cout << "OK\n";else {if (find(x) == find(y))cout << "OK but...\n";elsecout << "No way\n";}}return 0;
}