文章目录
题目描述输入描述输出描述用例题目解析JS算法源码Java算法源码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.处理消息：
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] += 1def 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 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;}