华为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.处理消息：

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;
}

作者：飞码创造者