刷题笔记合集🔗

题目描述

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

消息格式为 a b c，其中:

1. 整数a、b分别代表两个人的标号
2. 整数c代表指令:
   • c == 0: a和b在一个团队内
   • c == 1: 判定a和b的关系
   • c为其他值: 输出'da pian zi'

输入格式

第一行: 两个整数n,m(1<=n,m<100000)

• n表示人数
• m表示消息数量

接下来m行，每行一条消息:

• 三个整数a b c
• 1<=a,b<=n
• 0<=c<=1

输出格式

根据每条消息输出一行:

1. 当c==1时:
   • 如果a和b在一个团队，输出'we are a team'
   • 否则输出'we are not a team'
2. 当c为其他值，或a/b超出范围时，输出'da pian zi'
3. 当n/m超出范围时，输出'NULL'

约束说明

• 1 <= n,m < 100000
• 1 <= a,b <= n
• 0 <= c <= 1

样例输入1

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

样例输出1

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

样例说明1

1. 前三条消息建立了两个团队:
   • 团队1: 1,2,3
   • 团队2: 4,5
2. 后四条消息判断关系:
   • 1和2在同一团队
   • 2和3在同一团队
   • 4和5在同一团队
   • 1和5不在同一团队

题目解析

本题的关键点在于:

1. 团队关系处理

   • 使用并查集维护团队关系
   • c==0时合并两个人所在团队
   • c==1时判断是否在同一团队

2. 异常处理

   • 检查n,m是否在范围内
   • 检查a,b是否在范围内
   • 检查c是否为合法值

3. 并查集实现

   • find操作查找团队代表
   • union操作合并两个团队
   • 路径压缩优化查找效率

时间复杂度: O(mα(n))，其中α是阿克曼函数的反函数

参考代码

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):
        px, py = self.find(x), self.find(y)
        if px != py:
            self.parent[py] = px

def solve():
    try:
        # 读取输入
        n, m = map(int, input().split())
        
        # 检查n,m范围
        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 a team")
            else:
                print("da pian zi")
                
    except:
        return

if __name__ == "__main__":
    solve()

#include <iostream>
#include <v