#P3068. we are a team(100分)
-
1000ms
Tried: 229
Accepted: 47
Difficulty: 3
所属公司 :
华为od
we are a team(100分)
题面描述:
题目要求根据给定的消息判断两个人是否在同一个团队中。输入的第一行为两个整数 n 和 m,表示有 n 个人和 m 条消息,接下来每行包含三个整数 a、b 和 c。当 c=0 时,表示 a 和 b 在同一个团队;当 c=1 时,需要判断 a 和 b 是否在同一个团队,并输出“we are a team”或“we are not a team”。如果 a 或 b 超出范围,或者 c 不为 0 或 1,则输出“da pian zi”。若 n 或 m 的值超出范围,则输出“NULL”。
思路:
并查集板子题。
题解思路
这道题本质上是一个典型的并查集(Union-Find)问题。题目要求我们判断是否两个人在同一个团队中,并且通过一些消息来动态维护和查询团队关系。
并查集的主要操作:
- 查找操作(Find): 查找一个元素属于哪个集合,主要是通过路径压缩优化,使得查找操作的时间复杂度接近常数时间。
- 合并操作(Union): 将两个元素所属的集合合并,通过按秩合并或路径压缩来优化操作。
解题步骤:
- 初始化时,假设每个人自成一个团队,因此每个人的父节点指向自己。
- 当接收到一条消息时,根据指令 c 来执行不同的操作:
- 如果 c=0,说明要将两个人所在的团队合并在一起,执行
merge操作。 - 如果 c=1,则要查询两个人是否在同一个团队,执行
find操作。如果结果相同,输出 "we are a team",否则输出 "we are not a team"。 - 如果输入的消息格式不合法,则输出 "da pian zi"。
- 如果 c=0,说明要将两个人所在的团队合并在一起,执行
- 特殊情况处理:如果 n 或 m 超出题目要求的范围(1≤n,m≤100000),直接输出 "NULL"。
cpp
#include <bits/stdc++.h>
using namespace std;
// 定义一个长整型别名
#define int long long
// n表示人数,m表示消息条数
int n, m;
// 最大人数上限
const int N = 1e5 + 10;
// p数组用于存储每个人的父节点,初始时每个人是自己的父节点
int p[N];
// 查找操作:查找x所在集合的代表节点(即根节点)
// 使用路径压缩优化,使得查询速度接近O(1)
int find(int x) {
// 如果x是自己的父节点,则返回x;否则递归查找其父节点,并将父节点更新为最终根节点
return p[x] == x ? x : p[x] = find(p[x]);
}
// 合并操作:将a和b所在的两个集合合并
void merge(int a, int b) {
// 查找a和b各自的根节点
int pa = find(a), pb = find(b);
// 如果a和b不在同一个集合中,则将a的根节点pa指向b的根节点pb
if (pa != pb) {
p[pa] = pb;
}
}
signed main() {
// 读取人数n和消息条数m
cin >> n >> m;
// 特殊情况处理:如果n或m超出题目要求范围,直接输出"NULL"
if (n < 1 || n > 100000 || m < 1 || m > 100000) {
cout << "NULL" << endl;
return 0;
}
// 初始化并查集,每个人的父节点初始时指向自己
for (int i = 1; i <= n; i++) p[i] = i;
// 处理每条消息
for (int i = 1; i <= m; i++) {
int a, b, c;
cin >> a >> b >> c;
// 如果消息格式不合法,输出"da pian zi"
if (a < 1 || a > n || b < 1 || b > n || (c != 0 && c != 1)) {
cout << "da pian zi" << endl;
continue;
}
// 如果c == 0,执行合并操作,将a和b合并到同一个团队
if (c == 0) {
merge(a, b);
}
// 如果c == 1,执行查询操作,判断a和b是否在同一个团队
else if (c == 1) {
// 分别查找a和b的根节点
int pa = find(a);
int pb = find(b);
// 如果根节点相同,说明a和b在同一个团队,输出"we are a team"
if (pa == pb) {
cout << "we are a team" << endl;
}
// 否则,输出"we are not a team"
else {
cout << "we are not a team" << endl;
}
}
}
}
python
# 定义最大人数上限
N = 100000 + 10
# 并查集数组,初始化时每个人的父节点指向自己
p = list(range(N))
# 查找操作:查找 x 所在集合的代表节点(即根节点)
# 使用路径压缩优化,使得查询速度接近 O(1)
def find(x):
if p[x] == x:
return x
else:
# 路径压缩,将 x 的父节点直接指向根节点
p[x] = find(p[x])
return p[x]
# 合并操作:将 a 和 b 所在的两个集合合并
def merge(a, b):
pa = find(a)
pb = find(b)
# 如果 a 和 b 不在同一个集合中,则将 a 的根节点指向 b 的根节点
if pa != pb:
p[pa] = pb
# 读取人数和消息条数
n, m = map(int, input().split())
# 特殊情况处理:如果 n 或 m 超出题目要求范围,直接输出 "NULL"
if n < 1 or n > 100000 or m < 1 or m > 100000:
print("NULL")
else:
# 初始化并查集,每个人的父节点初始时指向自己
for i in range(1, n + 1):
p[i] = i
# 处理每条消息
for _ in range(m):
a, b, c = map(int, input().split())
# 如果消息格式不合法,输出 "da pian zi"
if a < 1 or a > n or b < 1 or b > n or (c != 0 and c != 1):
print("da pian zi")
continue
# 如果 c == 0,执行合并操作,将 a 和 b 合并到同一个团队
if c == 0:
merge(a, b)
# 如果 c == 1,执行查询操作,判断 a 和 b 是否在同一个团队
elif c == 1:
pa = find(a)
pb = find(b)
# 如果根节点相同,说明 a 和 b 在同一个团队,输出 "we are a team"
if pa == pb:
print("we are a team")
# 否则,输出 "we are not a team"
else:
print("we are not a team")
java
import java.util.Scanner;
public class Main {
// 定义最大人数上限
static final int N = 100000 + 10;
// 并查集数组,初始化时每个人的父节点指向自己
static int[] p = new int[N];
// 查找操作:查找 x 所在集合的代表节点(即根节点)
// 使用路径压缩优化,使得查询速度接近 O(1)
public static int find(int x) {
if (p[x] == x) {
return x;
} else {
// 路径压缩,将 x 的父节点直接指向根节点
p[x] = find(p[x]);
return p[x];
}
}
// 合并操作:将 a 和 b 所在的两个集合合并
public static void merge(int a, int b) {
int pa = find(a);
int pb = find(b);
// 如果 a 和 b 不在同一个集合中,则将 a 的根节点指向 b 的根节点
if (pa != pb) {
p[pa] = pb;
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// 读取人数和消息条数
int n = sc.nextInt();
int m = sc.nextInt();
// 特殊情况处理:如果 n 或 m 超出题目要求范围,直接输出 "NULL"
if (n < 1 || n > 100000 || m < 1 || m > 100000) {
System.out.println("NULL");
return;
}
// 初始化并查集,每个人的父节点初始时指向自己
for (int i = 1; i <= n; i++) {
p[i] = i;
}
// 处理每条消息
for (int i = 0; i < m; i++) {
int a = sc.nextInt();
int b = sc.nextInt();
int c = sc.nextInt();
// 如果消息格式不合法,输出 "da pian zi"
if (a < 1 || a > n || b < 1 || b > n || (c != 0 && c != 1)) {
System.out.println("da pian zi");
continue;
}
// 如果 c == 0,执行合并操作,将 a 和 b 合并到同一个团队
if (c == 0) {
merge(a, b);
}
// 如果 c == 1,执行查询操作,判断 a 和 b 是否在同一个团队
else if (c == 1) {
int pa = find(a);
int pb = find(b);
// 如果根节点相同,说明 a 和 b 在同一个团队,输出 "we are a team"
if (pa == pb) {
System.out.println("we are a team");
} else {
// 否则,输出 "we are not a team"
System.out.println("we are not a team");
}
}
}
}
}
题目内容
总共有 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 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
样例2
输入
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