L2-010. 排座位

题目链接：https://www.patest.cn/contests/gplt/L2-010

并查集

下午打的时候什么都没用，直接上一个矩阵，没有考虑“甲是a的朋友，a是b的朋友，b是乙的朋友”这种多个人关系的情况，华丽WA。出来问了学长，用的是并查集，用一个矩阵来表示两人之间的敌对关系(写的时候还是WA了好多次，最后才发现是"No way"的"w"打成了大写QAQ)

代码如下：

 1 #include<cstdio>
 2 using namespace std;
 3 bool enemy[105][105];
 4 int pre[105];
 5 int Find(int a){
 6     if(a!=pre[a])pre[a]=Find(pre[a]);
 7     return pre[a];
 8 }
 9 void uion(int a,int b){
10     int t1=Find(a),t2=Find(b);
11     if(t1!=t2)pre[t1]=t2;
12 }
13 void make(int n){
14     for(int i=1;i<=n;i++)pre[i]=i;
15 }
16 int main(void){
17     int n,m,k;
18     scanf("%d%d%d",&n,&m,&k);
19     make(n);
20     while(m--){
21         int a,b,g;
22         scanf("%d%d%d",&a,&b,&g);
23         if(g==1)uion(a,b);
24         else enemy[a][b]=enemy[b][a]=1; //a和b是敌人
25     }
26     while(k--){
27         int a,b;
28         scanf("%d%d",&a,&b);
29         int ta=Find(a),tb=Find(b);
30         if(enemy[a][b]){
31             if(ta==tb)printf("OK but...
");
32             else printf("No way
");
33         }else{
34             if(ta==tb)printf("No problem
");
35             else printf("OK
");
36         }
37     }
38     return 0;
39 }