刷题笔记合集🔗

We Are A Team

问题描述

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

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

输入格式

1. 第一行包含两个整数 和 （），分别表示有 个人和 条消息。
2. 随后的 行，每行一条消息，消息格式为：（）。

输出格式

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

样例输出

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

样例解释

根据输入的消息，判断指定的两个人是否在同一个团队中，并输出相应的结果。

数据范围

题解

为了判定两个人是否在同一个团队中，可以使用并查集（Union-Find）数据结构。并查集可以高效地进行合并和查找操作，适用于动态连通性问题。

并查集介绍

并查集是一种数据结构，用于处理一些不相交集合的合并及查询问题。主要操作有两个：

1. 查找（Find）：确定元素属于哪个子集。它可以被用来确定两个元素是否属于同一个子集。
2. 合并（Union）：将两个子集合并成一个集合。

并查集通过使用一个数组 parent 来记录每个元素的父节点，并使用路径压缩和按秩合并来优化操作的时间复杂度。

1. 初始化并查集：创建一个并查集，初始化每个人的父节点为自己。
2. 处理消息：对于每条消息，首先检查 和 是否在合法范围内（）。如果不合法，输出 da pian zi。如果 ，将 和 合并到同一个集合中。如果 ，检查 和 是否在同一个集合中。如果在同一个集合中，输出 we are a team，否则输出 we are not a team。如果 为其他值，输出 da pian zi。

参考代码

• Python

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
    
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    
    def union(self, x, y):
        self.parent[self.find(x)] = self.find(y)

def main():
    n, m = map(int, input().split())
    
    # 检查输入范围
    if n < 1 or n >= 100000 or m < 1 or m >= 100000:
        print("NULL")
        return
    
    uf = UnionFind(n + 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")
            continue
        
        if c == 0:
            uf.union(a, b)
        elif c == 1:
            if uf.find(a) == uf.find(b):
                print("we are a team")
            else:
                print("we are not