L2-010 排座位（很好的一题）

天梯赛L2-010传送门

解题思路

这题出得不错(*╯^╰)

1. 我们注意到朋友关系是可以传递的，不妨用并查集（恍然大悟😮）

2. 又注意到敌人关系是直接的，不具有传递性，所以可以用一个邻接矩阵来存敌对关系（恍然大悟😮）

如果能想到上面两点，得胜已是定局(>^ω<)

但是我没想到o(╥﹏╥)o

不过现在会了ლ(´ڡ`ლ)😋

ac✅️代码

#include<iostream>
using namespace std;
int f[110],enemy[1010][1010];
int find(int x)
{if(f[x] != x) f[x] = find(f[x]);return f[x];
}
int main()
{int n,m,k;cin>>n>>m>>k;for(int i = 1 ; i <= n ; i++) f[i] = i;while(m--){int a,b,c;cin>>a>>b>>c;if(c == 1){int fa = find(a);int fb = find(b);if(fa != fb) f[fa] = fb;}if(c == -1){enemy[a][b] = 1;enemy[b][a] = 1;}}while(k--){int a,b;cin>>a>>b;if(find(a) == find(b) && enemy[a][b] == 0) cout <<"No problem\n";else if(find(a) != find(b) && enemy[a][b] == 0) cout<<"OK\n";else if(find(a) == find(b) && enemy[a][b] == 1) cout<<"OK but...\n";else if(enemy[a][b] == 1) cout<<"No way\n"; }return 0;
}