常州市网站制作,施工企业质量管理,公司网站制作需要多少钱,河南省财政厅经济建设网站OD统一考试 题解#xff1a; Java / Python / C 题目描述
总共有 n 个人在机房#xff0c;每个人有一个标号 (1标号n) #xff0c;他们分成了多个团队#xff0c;需要你根据收到的 m 条消息判定指定的两个人是否在一个团队中#xff0c;具体的:
消息构成为 a b … OD统一考试 题解 Java / Python / 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”。
输入描述
第一行包含两个整数 nm(1n.m100000).分别表示有n个人和 m 条消息。随后的 m 行每行一条消息消息格式为: a b c (1a,bn, 0c1)
输出描述
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, c0) - 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 vectorusing 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(vectorint fa, int x) {if(fa[x] ! x) {fa[x] find(fa, fa[x]);}return fa[x];
}int merge(vectorint 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;}vectorint fa(n1);for(int i0; in; i) fa[i] i;for(int i0, a, b, c; im; 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 12021202. 交换字符串中的元素中等LeetCode 17221722. 执行交换操作后的最小汉明距离中等LeetCode 947947. 移除最多的同行或同列石头中等LeetCode 924924. 尽量减少恶意软件的传播困难
整理题解不易 如果有帮助到您请给点个赞 ❤️ 和收藏 ⭐让更多的人看到。
