pta l2-10（排座位）

题目链接：https://pintia.cn/problem-sets/994805046380707840/problems/994805066135879680

题意：给宴席排座位，有n个人，m个关系，k组询问，1表示为朋友，-1表示为敌人。询问时，两人为朋友而非敌人输出No problem，两人既不为敌人也不为朋友输出OK，两人为敌人但有共同的朋友输出OK but...，两人只有敌人关系输出No way。

思路：并查集，题目看着很绕，其实仔细看就会发现很简单。我们把有朋友关系的人并起来，但这个集合里也可能有敌人关系，然后用二维数组is[i][j]记录i,j是否是敌人，即两个人之间可能有4种关系：

有共同祖先，不敌对：No problem;
有共同祖先，敌对：OK but...
没有共同的祖先，不敌对：OK
没有共同的祖先，敌对：No way

AC代码：

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 
 4 int root[105],is[105][105],n,m,k;
 5 
 6 int getr(int kk){
 7     if(root[kk]==kk) return kk;
 8     else return root[kk]=getr(root[kk]);
 9 }
10 
11 int main(){
12     scanf("%d%d%d",&n,&m,&k);
13     for(int i=1;i<=n;++i)
14         root[i]=i;
15     int a,b,c;
16     while(m--){
17         scanf("%d%d%d",&a,&b,&c);
18         if(c==1){
19             int ar=getr(a),br=getr(b);
20             if(ar!=br)
21                 root[br]=ar;
22         }
23         else
24             is[a][b]=is[b][a]=1;
25     }
26     while(k--){
27         scanf("%d%d",&a,&b);
28         int ar=getr(a),br=getr(b);
29         if(ar==br&&!is[a][b]) printf("No problem
");
30         else if(ar==br&&is[a][b]) printf("OK but...
");
31         else if(ar!=br&&!is[a][b]) printf("OK
");
32         else printf("No way
");
33     }
34     return 0;
35 }