题面描述:

题目要求根据给定的消息判断两个人是否在同一个团队中。输入的第一行为两个整数 $n$ 和 $m$，表示有 $n$ 个人和 $m$ 条消息，接下来每行包含三个整数 $a$、$b$ 和 $c$。当 $c=0$ 时，表示 $a$ 和 $b$ 在同一个团队；当 $c=1$ 时，需要判断 $a$ 和 $b$ 是否在同一个团队，并输出“we are a team”或“we are not a team”。如果 $a$ 或 $b$ 超出范围，或者 $c$ 不为 0 或 1，则输出“da pian zi”。若 $n$ 或 $m$ 的值超出范围，则输出“NULL”。

思路:

并查集板子题。

题解思路

这道题本质上是一个典型的并查集（Union-Find）问题。题目要求我们判断是否两个人在同一个团队中，并且通过一些消息来动态维护和查询团队关系。

并查集的主要操作：

1. 查找操作（Find）： 查找一个元素属于哪个集合，主要是通过路径压缩优化，使得查找操作的时间复杂度接近常数时间。
2. 合并操作（Union）： 将两个元素所属的集合合并，通过按秩合并或路径压缩来优化操作。

解题步骤：

1. 初始化时，假设每个人自成一个团队，因此每个人的父节点指向自己。
2. 当接收到一条消息时，根据指令 $c$ 来执行不同的操作：
   • 如果 $c=0$，说明要将两个人所在的团队合并在一起，执行 merge 操作。
   • 如果 $c=1$，则要查询两个人是否在同一个团队，执行 find 操作。如果结果相同，输出 "we are a team"，否则输出 "we are not a team"。
   • 如果输入的消息格式不合法，则输出 "da pian zi"。
3. 特殊情况处理：如果 $n$ 或 $m$ 超出题目要求的范围（$1 \leq n,m \leq 100000$），直接输出 "NULL"。

cpp

#include <bits/stdc++.h>
using namespace std;

// 定义一个长整型别名
#define int long long

// n表示人数，m表示消息条数
int n, m;

// 最大人数上限
const int N = 1e5 + 10;

// p数组用于存储每个人的父节点，初始时每个人是自己的父节点
int p[N];

// 查找操作：查找x所在集合的代表节点（即根节点）
// 使用路径压缩优化，使得查询速度接近O(1)
int find(int x) {
    // 如果x是自己的父节点，则返回x；否则递归查找其父节点，并将父节点更新为最终根节点
    return p[x] == x ? x : p[x] = find(p[x]);
}

// 合并操作：将a和b所在的两个集合合并
void merge(int a, int b) {
    // 查找a和b各自的根节点
    int pa = find(a), pb = find(b);
    
    // 如果a和b不在同一个集合中，则将a的根节点pa指向b的根节点pb
    if (pa != pb) {
        p[pa] = pb;
    }
}

signed main() {
    // 读取人数n和消息条数m
    cin >> n >> m;

    // 特殊情况处理：如果n或m超出题目要求范围，直接输出"NULL"
    if (n < 1 || n > 100000 || m < 1 || m > 100000) {
        cout << "NULL" << endl;
        return 0;
    }

    // 初始化并查集，每个人的父节点初始时指向自己
    for (int i = 1; i <= n; i++) p[i] = i;

    // 处理每条消息
    for (int i = 1; i <= m; i++) {
        int a, b, c;
        cin >> a >> b >> c;

        // 如果消息格式不合法，输出"da pian zi"
        if (a < 1 || a > n || b < 1 || b > n || (c != 0 && c != 1)) {
            cout << "da pian zi" << endl;
            continue;
        }

        // 如果c == 0，执行合并操作，将a和b合并到同一个团队
        if (c == 0) {
            merge(a, b);
        }
        // 如果c == 1，执行查询操作，判断a和b是否在同一个团队
        else if (c == 1) {
            // 分别查找a和b的根节点
            int pa = find(a);
            int pb = find(b);

            // 如果根节点相同，说明a和b在同一个团队，输出"we are a team"
            if (pa == pb) {
                cout << "we are a team" << endl;
            }
            // 否则，输出"we are not a team"
            else {
                cout << "we are not a team" << endl;
            }
        }
    }
}

python

# 定义最大人数上限
N = 100000 + 10

# 并查集数组，初始化时每个人的父节点指向自己
p = list(range(N))

# 查找操作：查找 x 所在集合的代表节点（即根节点）
# 使用路径压缩优化，使得查询速度接近 O(1)
def find(x):
    if p[x] == x:
        return x
    else:
        # 路径压缩，将 x 的父节点直接指向根节点
        p[x] = find(p[x])
        return p[x]

# 合并操作：将 a 和 b 所在的两个集合合并
def merge(a, b):
    pa = find(a)
    pb = find(b)
    # 如果 a 和 b 不在同一个集合中，则将 a 的根节点指向 b 的根节点
    if pa != pb:
        p[pa] = pb

# 读取人数和消息条数
n, m = map(int, input().split())

# 特殊情况处理：如果 n 或 m 超出题目要求范围，直接输出 "NULL"
if n < 1 or n > 100000 or m < 1 or m > 100000:
    print("NULL")
else:
    # 初始化并查集，每个人的父节点初始时指向自己
    for i in range(1, n + 1):
        p[i] = i

    # 处理每条消息
    for _ in range(m):
        a, b, c = map(int, input().split())

        # 如果消息格式不合法，输出 "da pian zi"
        if a < 1 or a > n or b < 1 or b > n or (c != 0 and c != 1):
            print("da pian zi")
            continue

        # 如果 c == 0，执行合并操作，将 a 和 b 合并到同一个团队
        if c == 0:
            merge(a, b)
        # 如果 c == 1，执行查询操作，判断 a 和 b 是否在同一个团队
        elif c == 1:
            pa = find(a)
            pb = find(b)

            # 如果根节点相同，说明 a 和 b 在同一个团队，输出 "we are a team"
            if pa == pb:
                print("we are a team")
            # 否则，输出 "we are not a team"
            else:
                print("we are not a team")

java

import java.util.Scanner;

public class Main {
    // 定义最大人数上限
    static final int N = 100000 + 10;
    // 并查集数组，初始化时每个人的父节点指向自己
    static int[] p = new int[N];

    // 查找操作：查找 x 所在集合的代表节点（即根节点）
    // 使用路径压缩优化，使得查询速度接近 O(1)
    public static int find(int x) {
        if (p[x] == x) {
            return x;
        } else {
            // 路径压缩，将 x 的父节点直接指向根节点
            p[x] = find(p[x]);
            return p[x];
        }
    }

    // 合并操作：将 a 和 b 所在的两个集合合并
    public static void merge(int a, int b) {
        int pa = find(a);
        int pb = find(b);
        // 如果 a 和 b 不在同一个集合中，则将 a 的根节点指向 b 的根节点
        if (pa != pb) {
            p[pa] = pb;
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        // 读取人数和消息条数
        int n = sc.nextInt();
        int m = sc.nextInt();

        // 特殊情况处理：如果 n 或 m 超出题目要求范围，直接输出 "NULL"
        if (n < 1 || n > 100000 || m < 1 || m > 100000) {
            System.out.println("NULL");
            return;
        }

        // 初始化并查集，每个人的父节点初始时指向自己
        for (int i = 1; i <= n; i++) {
            p[i] = i;
        }

        // 处理每条消息
        for (int i = 0; i < m; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            int c = sc.nextInt();

            // 如果消息格式不合法，输出 "da pian zi"
            if (a < 1 || a > n || b < 1 || b > n || (c != 0 && c != 1)) {
                System.out.println("da pian zi");
                continue;
            }

            // 如果 c == 0，执行合并操作，将 a 和 b 合并到同一个团队
            if (c == 0) {
                merge(a, b);
            }
            // 如果 c == 1，执行查询操作，判断 a 和 b 是否在同一个团队
            else if (c == 1) {
                int pa = find(a);
                int pb = find(b);

                // 如果根节点相同，说明 a 和 b 在同一个团队，输出 "we are a team"
                if (pa == pb) {
                    System.out.println("we are a team");
                } else {
                    // 否则，输出 "we are not a team"
                    System.out.println("we are not a team");
                }
            }
        }
    }
}

题目内容

总共有 $n$ 个人在机房，每个人有一个标号（$1$<=标号<=$n$），他们分成了多个团队，需要你根据收到的 $m$ 条消息判定指定的两个人是否在一个团队中，具体的：

消息构成为 $a$ $b$ $c$，整数 $a$、$b$ 分别代表两个人的标号，整数 $c$ 代表指令

• $c$ == $0$ 代表 $a$ 和 $b$ 在一个团队内
• $c$ == $1$ 代表需要判定 $a$ 和 $b$ 的关系，如果 $a$ 和 $b$ 是一个团队，输出一行’$we$ $are$ $a$ $team$’,如果不是，输出一行’$we$ $are$ $not$ $a$ $team$’
• $c$ 为其他值，或当前行 $a$ 或 $b$ 超出 $1$~$n$ 的范围，输出‘$da$ $pian$ $zi$’

输入描述

第一行包含两个整数 $n，m(1<=n,m<100000)$,分别表示有 $n$ 个人和 $m$ 条消息

随后的 $m$ 行，每行一条消息，消息格式为：$a$ $b$ $c(1<=a,b<=n,0<=c<=1)$

输出描述

$c$ ==$1$,根据 $a$ 和 $b$ 是否在一个团队中输出一行字符串，在一个团队中输出‘$we$ $are$ $a$ $team$‘,不在一个团队中输出’$we$ $are$ $not$ $a$ $team$’

$c$ 为其他值，或当前行 $a$ 或 $b$ 的标号小于 $1$ 或者大于 $n$ 时，输出字符串‘$da$ $pian$ $zi$‘

如果第一行 $n$ 和 $m$ 的值超出约定的范围时，输出字符串”$NULL$“。

样例1

输入

5 7
1 2 0
4 5 0
2 3 0
1 2 1
2 3 1
4 5 1
1 5 1

输出

we are a team
we are a team
we are a team
we are not a team

样例2

输入

5 6
1 2 0
1 2 1
1 5 0
2 3 1
2 5 1
1 3 2

输出

we are a team
we are not a team
we are a team
da pian zi