刷题笔记合集🔗

We Are A Team

问题描述

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

1. 消息构成为 ，整数 、 分别代表两个人的标号，整数 代表指令
2. 代表 和 在一个团队内
3. 代表需要判定 和 的关系，如果 和 是一个团队，输出一行'we are a team'，如果不是，输出一行'we are not a team'
4. 为其他值，或当前行 或 超出 的范围，输出'da pian zi'

输入格式

第一行包含两个整数 ，（），分别表示有 个人和 条消息。

随后的 行，每行一条消息，消息格式为： （，）。

输出格式

1. 时，根据 和 是否在一个团队中输出一行字符串，在一个团队中输出'we are a team'，不在一个团队中输出'we are not a team'
2. 为其他值，或当前行 或 的标号小于 1 或者大于 时，输出字符串'da pian zi'
3. 如果第一行 和 的值超出约定的范围时，输出字符串"NULL"

样例输入

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

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 a team
we are a team
we are not a team

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

数据范围

题解

这道题目是一个典型的"并查集"（Union-Find Set）应用场景。并查集是一种用于管理元素所属集合的数据结构，支持两种操作：

1. 合并（Union）：将两个元素所在的集合合并为一个集合
2. 查找（Find）：查询某个元素所在的集合，通常返回该集合的代表元素

对于这个问题，我们可以将每个人视为并查集中的一个元素，初始时每个人各自为一个集合。然后根据消息进行操作：

1. 当 c=0 时，执行合并操作，将a和b所在的集合合并
2. 当 c=1 时，执行查找操作，判断a和b是否在同一个集合中
3. 其他情况需要按题目要求输出特定信息

在实现并查集时，通常使用一个数组来记录每个元素的父节点。初始时，每个元素的父节点是自己。合并操作是将其中一个集合的代表元素指向另一个集合的代表元素，从而将两个集合连接起来。查找操作是沿着父节点一直向上追溯，直到找到集合的代表元素（其父节点是自己的元素）。

为了提高效率，并查集通常采用两种优化：

1. 路径压缩：在查找操作时，将沿途经过的所有节点直接连接到根节点，减少后续查找的路径长度
2. 按秩合并：合并时，将较小的树连接到较大的树上，避免树高度增加过快

时间复杂度：假设并查集操作的平均时间复杂度接近O(1)，那么总的时间复杂度就是O(m)，其中m是消息的数量。

空间复杂度：需要一个大小为n+1的数组来存储并查集，因此空间复杂度为O(n)。

参考代码

• Python

import sys
input = lambda:sys.stdin.readline().strip()

# 读取输入
n, m = map(int, input().split())

# 并查集实现
class UnionFind:
    def __init__(self, size):
        # 初始化父节点数组，每个元素的父节点是自己
        self.parent = list(range(size))
    
    def find(self, x):
        # 查找元素x所在集合的代表元素，并进行路径压缩
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    
    def union(self, x, y):
        # 合并元素x和y所在的集合
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x != root_y:
            self.parent[root_y] = root_x

# 检查输入参数是否合法
if n < 1 or n >= 100000 or m < 1 or m >= 100000:
    print("NULL")
else:
    # 创建并查集对象
    uf = UnionFind(n + 1)  # +1是因为人的编号从1开始
    
    # 处理每条消息
    for _ in range(m):
        a, b, c = map(int, input().split())
        
        # 检查a和b是否在有效范围内
        if a < 1 or a > n or b < 1 or b > n:
            print("da pian zi")
        elif c == 0:
            # 合并操作
            uf.union(a, b)
        elif c == 1:
            # 查询操作
            if uf.find(a) == uf.find(b):
                print("we are a team")