L2-010 排座位

#include <stdio.h>
#include <stdlib.h>

#define MAXN 101

int parent[MAXN]; // 并查集的父节点数组，用于存储每个宾客的根节点
int enemy[MAXN][MAXN]; // 敌对关系邻接表，记录每对宾客之间的敌对关系

// 并查集：查找根节点
int find(int x) {
    if (parent[x] == x) return x; // 如果 x 是自己的根节点，直接返回 x
    return parent[x] = find(parent[x]); // 路径压缩：将 x 的父节点设置为根节点，并返回根节点
}

// 并查集：合并两个集合
void unite(int x, int y) {
    int rootX = find(x); // 找到 x 的根节点
    int rootY = find(y); // 找到 y 的根节点
    if (rootX != rootY) {
        parent[rootX] = rootY; // 如果根节点不同，将 x 的根节点指向 y 的根节点
    }
}

int main() {
    int N, M, K;
    scanf("%d %d %d", &N, &M, &K); // 读取宾客总数 N，关系数 M，查询数 K

    // 初始化并查集
    for (int i = 1; i <= N; i++) {
        parent[i] = i; // 每个宾客初始时是自己的根节点
    }

    // 处理关系
    for (int i = 0; i < M; i++) {
        int a, b, r;
        scanf("%d %d %d", &a, &b, &r); // 读取一对关系：宾客 a，宾客 b，关系 r
        if (r == 1) {
            unite(a, b); // 如果是朋友关系，合并 a 和 b 的集合
        } else if (r == -1) {
            enemy[a][b] = 1; // 如果是敌对关系，记录 a 和 b 之间的敌对关系
            enemy[b][a] = 1; // 敌对关系是双向的，同时记录 b 和 a 之间的敌对关系
        }
    }

    // 处理查询
    for (int i = 0; i < K; i++) {
        int a, b;
        scanf("%d %d", &a, &b); // 读取一对查询：宾客 a 和宾客 b

        int rootA = find(a); // 找到 a 的根节点
        int rootB = find(b); // 找到 b 的根节点

        if (rootA == rootB && !enemy[a][b]) {
            // 如果 a 和 b 是朋友且没有敌对关系
            printf("No problem\n");
        } else if (rootA != rootB && !enemy[a][b]) {
            // 如果 a 和 b 不是朋友且没有敌对关系
            printf("OK\n");
        } else if (enemy[a][b] && rootA == rootB) {
            // 如果 a 和 b 有敌对关系，但有共同朋友
            printf("OK but...\n");
        } else if (enemy[a][b]) {
            // 如果 a 和 b 只有敌对关系
            printf("No way\n");
        }
    }

    return 0; // 程序正常结束
}