华为OD机试E卷 --we are a team--24年OD统一考试（Java JS Python C C++）

题目描述

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

1. 消息构成为 a b c，整数 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 行，每行一条消息，消息格式为：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 的标号小于 1 或者大于 n 时，输出字符串‘da pian zi‘
3. 如果第一行 n 和 m 的值超出约定的范围时，输出字符串”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

说明
无

输入

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

说明
无

题目解析

这个问题可以看作是一个并查集（Union-Find）问题。并查集是一种数据结构，用于处理一些不交集（Disjoint Sets）的合并及查询问题。在这个问题中，我们需要根据输入的消息动态地合并团队，并查询两个人是否在同一团队中。

1.初始化：首先，我们需要初始化一个并查集，每个人最初都是一个独立的团队。
2.处理消息：

• 如果 c == 0，则合并 a 和 b 所在的团队。
• 如果 c == 1，则查询 a 和 b 是否在同一团队中，并输出相应的结果。
• 如果 c 为其他值，或者 a 或 b 的标号不在 1 到 n 的范围内，输出 da pian zi。

3.边界条件：如果输入的 n 或 m 超出范围，输出 NULL。

JS算法源码

function findRoot(parent, i) {if (parent[i] !== i) {parent[i] = findRoot(parent, parent[i]);}return parent[i];
}function union(parent, rank, x, y) {let rootX = findRoot(parent, x);let rootY = findRoot(parent, y);if (rootX !== rootY) {if (rank[rootX] > rank[rootY]) {parent[rootY] = rootX;} else if (rank[rootX] < rank[rootY]) {parent[rootX] = rootY;} else {parent[rootY] = rootX;rank[rootX]++;}}
}function main() {const input = require('fs').readFileSync(0, 'utf8').trim().split('\n');const [nStr, mStr] = input[0].split(' ').map(Number);if (nStr < 1 || nStr >= 100000 || mStr < 1 || mStr >= 100000) {console.log("NULL");return;}const n = nStr;const m = mStr;const messages = input.slice(1).map(line => line.split(' ').map(Number));const parent = [];const rank = [];for (let i = 1; i <= n; i++) {parent[i] = i;rank[i] = 0;}for (const [a, b, c] of messages) {if (a < 1 || a > n || b < 1 || b > n || c < 0 || c > 1) {console.log("da pian zi");} else if (c === 0) {union(parent, rank, a, b);} else if (c === 1) {if (findRoot(parent, a) === findRoot(parent, b)) {console.log("we are a team");} else {console.log("we are not a team");}}}
}main();

Java算法源码

import java.util.*;public class Main {static int[] parent;static int[] rank;static int findRoot(int i) {if (parent[i] != i) {parent[i] = findRoot(parent[i]);}return parent[i];}static void union(int x, int y) {int rootX = findRoot(x);int rootY = findRoot(y);if (rootX != rootY) {if (rank[rootX] > rank[rootY]) {parent[rootY] = rootX;} else if (rank[rootX] < rank[rootY]) {parent[rootX] = rootY;} else {parent[rootY] = rootX;rank[rootX]++;}}}public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();int m = scanner.nextInt();if (n < 1 || n >= 100000 || m < 1 || m >= 100000) {System.out.println("NULL");return;}parent = new int[n + 1];rank = new int[n + 1];for (int i = 1; i <= n; i++) {parent[i] = i;rank[i] = 0;}for (int i = 0; i < m; i++) {int a = scanner.nextInt();int b = scanner.nextInt();int c = scanner.nextInt();if (a < 1 || a > n || b < 1 || b > n || c < 0 || c > 1) {System.out.println("da pian zi");} else if (c == 0) {union(a, b);} else if (c == 1) {if (findRoot(a) == findRoot(b)) {System.out.println("we are a team");} else {System.out.println("we are not a team");}}}}
}

python算法源码

def find_root(parent, i):if parent[i] != i:parent[i] = find_root(parent, parent[i])return parent[i]def union(parent, rank, x, y):rootX = find_root(parent, x)rootY = find_root(parent, y)if rootX != rootY:if rank[rootX] > rank[rootY]:parent[rootY] = rootXelif rank[rootX] < rank[rootY]:parent[rootX] = rootYelse:parent[rootY] = rootXrank[rootX] += 1def main():import sysinput = sys.stdin.read().strip().split('\n')n, m = map(int, input[0].split())if n < 1 or n >= 100000 or m < 1 or m >= 100000:print("NULL")returnmessages = [list(map(int, line.split())) for line in input[1:]]parent = [i for i in range(1, n + 1)]rank = [0] * (n + 1)for a, b, c in messages:if a < 1 or a > n or b < 1 or b > n or c < 0 or c > 1:print("da pian zi")elif c == 0:union(parent, rank, a, b)elif c == 1:if find_root(parent, a) == find_root(parent, b):print("we are a team")else:print("we are not a team")if __name__ == "__main__":main()

c算法源码

#include <stdio.h>
#include <stdlib.h>#define MAXN 100000int parent[MAXN];int find(int x) {if (parent[x] != x) {parent[x] = find(parent[x]);}return parent[x];
}void unionSets(int a, int b) {int rootA = find(a);int rootB = find(b);if (rootA != rootB) {parent[rootA] = rootB;}
}int main() {int n, m;scanf("%d %d", &n, &m);if (n < 1 || n > MAXN || m < 1 || m > MAXN) {printf("NULL\n");return 0;}for (int i = 1; i <= n; i++) {parent[i] = i;}for (int i = 0; i < m; i++) {int a, b, c;scanf("%d %d %d", &a, &b, &c);if (a < 1 || a > n || b < 1 || b > n || (c != 0 && c != 1)) {printf("da pian zi\n");} else if (c == 0) {unionSets(a, b);} else if (c == 1) {if (find(a) == find(b)) {printf("we are a team\n");} else {printf("we are not a team\n");}}}return 0;
}

c++算法源码

#include <iostream>
#include <vector>using namespace std;class UnionFind {
public:UnionFind(int n) {parent.resize(n + 1);for (int i = 1; i <= n; i++) {parent[i] = i;}}int find(int x) {if (parent[x] != x) {parent[x] = find(parent[x]);}return parent[x];}void unionSets(int a, int b) {int rootA = find(a);int rootB = find(b);if (rootA != rootB) {parent[rootA] = rootB;}}private:vector<int> parent;
};int main() {int n, m;cin >> n >> m;if (n < 1 || n > 100000 || m < 1 || m > 100000) {cout << "NULL" << endl;return 0;}UnionFind uf(n);for (int i = 0; i < m; i++) {int a, b, c;cin >> a >> b >> c;if (a < 1 || a > n || b < 1 || b > n || (c != 0 && c != 1)) {cout << "da pian zi" << endl;} else if (c == 0) {uf.unionSets(a, b);} else if (c == 1) {if (uf.find(a) == uf.find(b)) {cout << "we are a team" << endl;} else {cout << "we are not a team" << endl;}}}return 0;
}