We are a team - 华为OD统一考试

OD统一考试

题解： Java / Python / C++

alt

题目描述

总共有 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 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

题解

并查集的简单模板套用

如果对并查集不会，可以通过 https://zhuanlan.zhihu.com/p/93647900 来学习。

Java

import java.util.Scanner;
public class Main {private static boolean checkRange(int a, int b, int c) {return 1 <= a && a <= 100000 && 1 <= b && b <= 100000 && 0 <= c && c <= 1;}public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt(), m = scanner.nextInt();if (!checkRange(n, m, 0)) {System.out.println("NULL");return;}UnionFind uf = new UnionFind(n);for (int i = 0; i < m; i++) {int a = scanner.nextInt(), b = scanner.nextInt(), c = scanner.nextInt();if (checkRange(a, b, c)) {if (c == 0) {uf.merge(a, b);} else if (uf.find(a) == uf.find(b)) {System.out.println("we are a team");} else {System.out.println("we are not a team");}} else {System.out.println("da pian zi");}}}}/*** 并查集** @Description: 学习参考： https://zhuanlan.zhihu.com/p/93647900* @Author code5bug* @Date 20-10-22* @Version 1.0**/
class UnionFind {// father[2] = 3 表示元素2的父节点是3public int[] father;public UnionFind(int len) {father = new int[len + 1];for (int i = 1; i <= len; i++) {father[i] = i;}}// 查询 x 的根节点public int find(int x) {if (x < 0 || x >= father.length) {throw new RuntimeException("查询越界");}// 合并（路径压缩）return (x == father[x] ? x : (father[x] = find(father[x])));}// 合并节点, y 的根节点指向 x 的根节点public void merge(int x, int y) {int xRoot = find(x), yRoot = find(y);father[yRoot] = xRoot;}
}

Python

n, m = map(int, input().split())def check_range(a: int, b: int, c=0) -> bool:return 1 <= a <= 100000 and 1 <= b <= 100000 and 0 <= c <= 1if check_range(n, m):fa = [i for i in range(n + 1)]def find(x: int) -> int:if fa[x] != x:fa[x] = find(fa[x])return fa[x]def merge(x: int, y: int):x_root, y_root = find(x), find(y)fa[x_root] = y_rootfor _ in range(m):a, b, c = map(int, input().split())if check_range(a, b, c):if c == 0:merge(a, b)elif find(a) == find(b):print("we are a team")else:print("we are not a team")else:print("da pian zi")
else:print("NULL")

C++

#include <iostream>
#include <vector>using namespace std;bool check_range(int a, int b, int c = 0) {if(a < 1 || b < 1 || c < 0) return false;if(a > 100000 || b > 100000 || c > 1) return false;return true;
}int find(vector<int>& fa, int x) {if(fa[x] != x) {fa[x] = find(fa, fa[x]);}return fa[x];
}int merge(vector<int>& fa, int x, int y) {int xRoot = find(fa, x), yRoot = find(fa, y);fa[xRoot] = yRoot;
}int main() {int n, m;cin >> n >> m;if(!check_range(n, m)) {cout << "NULL" << endl;return -1;}vector<int> fa(n+1);for(int i=0; i<=n; i++) fa[i] = i;for(int i=0, a, b, c; i<m; i++) {cin >> a >> b >> c;if(check_range(a, b, c)) {if(c == 0) {merge(fa, a, b);} else if(find(fa, a) == find(fa, b)) {cout << "we are a team" << endl;} else {cout << "we are not a team" << endl;}} else {cout << "da pian zi" << endl;}}return 0;
}

（并查集）相关练习题

题号	题目	难易
LeetCode 1202	1202. 交换字符串中的元素	中等
LeetCode 1722	1722. 执行交换操作后的最小汉明距离	中等
LeetCode 947	947. 移除最多的同行或同列石头	中等
LeetCode 924	924. 尽量减少恶意软件的传播	困难