PTA 数据结构排座位（并查集）

分手后的思念是犯贱 2022-05-15 14:19 193阅读 0赞

7-2 排座位 （25 分）

布置宴席最微妙的事情，就是给前来参宴的各位宾客安排座位。无论如何，总不能把两个死对头排到同一张宴会桌旁！这个艰巨任务现在就交给你，对任何一对客人，请编写程序告诉主人他们是否能被安排同席。

### 输入格式： ###

输入第一行给出3个正整数：`N`（≤100），即前来参宴的宾客总人数，则这些人从1到`N`编号；`M`为已知两两宾客之间的关系数；`K`为查询的条数。随后`M`行，每行给出一对宾客之间的关系，格式为：`宾客1 宾客2 关系`，其中`关系`为1表示是朋友，-1表示是死对头。注意两个人不可能既是朋友又是敌人。最后`K`行，每行给出一对需要查询的宾客编号。

这里假设朋友的朋友也是朋友。但敌人的敌人并不一定就是朋友，朋友的敌人也不一定是敌人。只有单纯直接的敌对关系才是绝对不能同席的。

### 输出格式： ###

对每个查询输出一行结果：如果两位宾客之间是朋友，且没有敌对关系，则输出`No problem`；如果他们之间并不是朋友，但也不敌对，则输出`OK`；如果他们之间有敌对，然而也有共同的朋友，则输出`OK but...`；如果他们之间只有敌对关系，则输出`No way`。

### 输入样例： ###

7 8 4
    5 6 1
    2 7 -1
    1 3 1
    3 4 1
    6 7 -1
    1 2 1
    1 4 1
    2 3 -1
    3 4
    5 7
    2 3
    7 2

### 输出样例： ###

No problem
    OK
    OK but...
    No way

用并查集存储朋友关系，二维数组存储敌人关系

另外，如果加了using namespace std，并用-std=c++14进行编译会报错，提示error: reference to 'rank' is ambiguous,这是因为有std::rank这个东西，所以数组名不能再用rank。

#include <iostream>
    #include <cstdio>
    #include <cstdlib>
    
    int node[110]; //每个节点
    int rank[110]; //树的高度
    
    //初始化n个节点
    void Init(int n){
        for(int i = 1; i <= n; i++){
            node[i] = i;
            rank[i] = 1;
        }
    }
    //查找当前元素所在树的根节点(代表元素)
    int find(int x){
        if(x == node[x])
            return x;
        return node[x] = find(node[x]); //在第一次查找时，将节点直连到根节点
    }
    //合并元素x， y所处的集合
    void Unite(int x, int y){
        //查找到x，y的根节点
        x = find(x);
        y = find(y);
        if(x == y)
            return ;
        //判断两棵树的高度，然后在决定谁为子树
        if(rank[x] < rank[y]){
            node[x] = y;
        }else{
            node[y] = x;
            if(rank[x] == rank[y]) rank[x]++;
        }
    }
    //判断x，y是属于同一个集合
    bool same(int x, int y){
        return find(x) == find(y);
    }
    
    int main()
    {
        int enemy[110][110] = {0};
        int N,M,K;
        std::cin>>N>>M>>K;
        Init(N);
        int person1,person2,relation;
        while(M--)
        {
            std::cin>>person1>>person2>>relation;
            if(relation==1)
                Unite(person1,person2);
            else
            {
                enemy[person1][person2] = 1;
                enemy[person2][person1] = 1;
            }
        }
        while(K--)
        {
            std::cin>>person1>>person2;
            if(same(person1,person2) && !enemy[person1][person2])
                std::cout<<"No problem"<<std::endl;
            else if(!same(person1,person2) && !enemy[person1][person2])
                std::cout<<"OK"<<std::endl;
            else if(same(person1,person2) && enemy[person1][person2])
                std::cout<<"OK but..."<<std::endl;
            else
                std::cout<<"No way"<<std::endl;
        }
        return 0;
    }