华为OD机试E卷 --we are a team--24年OD统一考试（Java & JS & Python & C & C++）
题目描述
总共有 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“。
用例
输入
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] = rootX
elif rank[rootX] < rank[rootY]:
parent[rootX] = rootY
else:
parent[rootY] = rootX
rank[rootX] += 1
def main():
import sys
input = 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")
return
messages = [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 100000
int 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;
}
原文地址：https://blog.csdn.net/wbajsjhhhhh/article/details/143997212
免责声明：本站文章内容转载自网络资源，如侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！