华为OD机试真题---We Are A Team

华为OD机试真题“We Are A Team”是一道涉及并查集数据结构的题目。以下是该题目的详细解析：

一、题目描述

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

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

二、输入描述

1. 第一行包含两个整数n和m（1<=n, m<100000），分别表示有n个人和m条消息。
2. 随后的m行，每行一条消息，消息格式为abc（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的标号小于1或者大于n时，输出字符串“da pian zi”。
3. 如果第一行n和m的值超出约定的范围时，输出字符串“NULL”。

四、解题思路

1. 初始化：根据输入的n和m，判断是否超出约定的范围。如果超出则输出“NULL”。然后，创建一个长度为n+1的数组parent（或称为father），用于存储每个人的父节点。初始时，每个元素的父节点都是自己。

2. 遍历消息：对于每条消息a、b、c，进行如下操作：

   • 如果c==0，表示a和b在同一个团队中，需要将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”。

3. 查找根节点：为了实现快速的团队查找和合并，可以使用路径压缩的并查集。在查找某个元素的根节点时，如果该元素的父节点不是它自己，则递归地查找其父节点的根节点，并将路径上的每个节点直接连接到根节点上，以实现路径压缩。

五、代码实现

以下是该题目的Python代码实现：

class UnionFind:def __init__(self, n):self.parent = list(range(n))self.rank = [0] * 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):x_root = self.find(x)y_root = self.find(y)if x_root != y_root:# 按秩合并if self.rank[x_root] < self.rank[y_root]:self.parent[x_root] = y_rootelif self.rank[x_root] > self.rank[y_root]:self.parent[y_root] = x_rootelse:self.parent[y_root] = x_rootself.rank[x_root] += 1def main():n, m = map(int, input().split())if n < 1 or n >= 100000 or m < 1 or m >= 100000:print("NULL")returnmsgs = [list(map(int, input().split())) for _ in range(m)]uf = UnionFind(n + 1)for a, b, c in msgs: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")if __name__ == "__main__":main()

该代码首先定义了一个UnionFind类，用于实现并查集的功能。然后，在main函数中读取输入，并根据输入的消息进行相应的操作。注意，在读取消息时，我们使用了列表推导式来简化代码。同时，在判断c的值时，如果c不为0或1，则直接输出“da pian zi”。

---

以下是该题目的java代码实现：

在Java中实现“We Are A Team”题目，我们需要创建一个类来封装并查集（Union-Find）的逻辑，并在主程序中读取输入、处理消息以及输出结果。以下是一个可能的Java实现：

import java.util.Scanner;class UnionFind {private int[] parent;private int[] rank;/*** 构造函数，初始化并查集** @param n 集合的大小*/public UnionFind(int n) {parent = new int[n + 1];rank = new int[n + 1];for (int i = 1; i <= n; i++) {parent[i] = i;}}/*** 查找元素的根节点，并进行路径压缩** @param x 元素* @return 元素的根节点*/public int find(int x) {if (parent[x] != x) {parent[x] = find(parent[x]); // 路径压缩}return parent[x];}/*** 合并两个集合* 此方法用于合并包含x和y的两个集合通过使用按秩合并的策略来优化合并过程** @param x 集合中的一个元素* @param y 集合中的另一个元素*/public void union(int x, int y) {// 找到x的根节点int xRoot = find(x);// 找到y的根节点int yRoot = find(y);// 如果x和y的根节点不同，则进行合并if (xRoot != yRoot) {// 如果x的根节点的秩小于y的根节点的秩，则将x的根节点挂接到y的根节点下if (rank[xRoot] < rank[yRoot]) {parent[xRoot] = yRoot;// 如果x的根节点的秩大于y的根节点的秩，则将y的根节点挂接到x的根节点下} else if (rank[xRoot] > rank[yRoot]) {parent[yRoot] = xRoot;// 如果x的根节点的秩等于y的根节点的秩，则选择将y的根节点挂接到x的根节点下，并增加x的根节点的秩} else {parent[yRoot] = xRoot;rank[xRoot]++;}}}
}public class WeAreATeam {public static void main(String[] args) {// 创建Scanner对象以读取输入Scanner scanner = new Scanner(System.in);// 读取n和mint n = scanner.nextInt();int m = scanner.nextInt();// 检查n和m的范围if (n < 1 || n >= 100000 || m < 1 || m >= 100000) {System.out.println("NULL");return;}// 创建并查集UnionFind uf = new UnionFind(n);// 处理m条消息for (int i = 0; i < m; i++) {int a = scanner.nextInt();int b = scanner.nextInt();int c = scanner.nextInt();// 检查a和b的范围if (a < 1 || a > n || b < 1 || b > n) {System.out.print("da pian zi");continue;}// 处理消息if (c == 0) {uf.union(a, b);} else if (c == 1) {if (uf.find(a) == uf.find(b)) {System.out.print("we are a team");} else {System.out.print("we are not a team");}} else {System.out.print("da pian zi");}}// 关闭扫描器scanner.close();}
}

六、代码说明：

1. UnionFind 类：

   • parent 数组存储每个节点的父节点。
   • rank 数组用于记录树的深度，以实现按秩合并。
   • find 方法查找节点的根，并应用路径压缩。
   • union 方法合并两个节点所在的集合。

2. WeAreATeam 类（包含 main 方法）：

   • 使用 Scanner 读取输入。
   • 检查 n 和 m 的范围，如果超出范围则输出 “NULL”。
   • 创建 UnionFind 实例。
   • 循环处理 m 条消息，根据 c 的值执行相应的操作：
     • 如果 c == 0，则调用 union 方法合并 a 和 b。
     • 如果 c == 1，则检查 a 和 b 是否在同一个集合中，并输出相应的结果。
     • 如果 c 为其他值，或者 a 和 b 的范围不正确，则输出 “da pian zi”。

七、运行示例解析

首先，我们来看您提供的Java代码和输入示例。您的代码实现了一个并查集（Union-Find）数据结构，用于处理动态连通性问题。输入包括两个整数n和m，分别表示集合中元素的数量和操作的数量。接下来的m行，每行包含三个整数a, b, c，其中a和b是集合中的元素（在您的代码中，这些元素是从1开始编号的，这与并查集数组索引通常从0开始的习惯不同，但您已经在代码中做了适当的调整），c表示要执行的操作类型：0表示合并a和b所在的集合，1表示查询a和b是否在同一集合中。

现在，我们来逐步解析输入示例：

输入：

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

1. 初始化：

   • n = 5，表示有5个元素（编号为1到5）。
   • m = 4，表示有4个操作。
   • 创建一个大小为6（因为数组索引从0开始，而元素编号从1开始）的并查集。

2. 第一个操作：1 2 0

   • 合并元素1和2所在的集合。
   • 并查集状态变化：{1, 2}, {3}, {4}, {5}（这里用集合表示元素之间的连通性）。

3. 第二个操作：3 4 0

   • 合并元素3和4所在的集合。
   • 并查集状态变化：{1, 2}, {3, 4}, {5}。

4. 第三个操作：1 3 1

   • 查询元素1和3是否在同一集合中。
   • 由于1在{1, 2}中，而3在{3, 4}中，它们不在同一集合中。
   • 输出：we are not a team

5. 第四个操作：2 5 1

   • 查询元素2和5是否在同一集合中。
   • 由于2在{1, 2}中，而5在{5}中，它们不在同一集合中。
   • 输出：we are not a team