华为OD机试 We are 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 c1<=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 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

考点 并查集

#include <bits/stdc++.h>
using namespace std;
int find(vector<int>v, int s) {//定义一个find函数 用于查询根节点
    while (v[s] >= 0) {
        s = v[s];
    }
    return s;
}
int main() {
    int m = 0, n = 0;
    cin >> m >> n;
    if ((n < 1 || m > 100000)) {
        cout << "NULL";
        return  -1;
    }
    vector<int>p1(m + 1, -1);//并查集 一维数组实现
    vector<vector<int>>p2;//保存判定语句用的二维数组
    int d = 0;
    for (int i = 0; i < n; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        if (a<1 || a>n || b<1 || b>n) {
            cout << "da pian zi";
            return  -1;
        }
        if (c == 0)//并查集记录节点关系
            p1[b] = a;
        else if (c != 0) {//记录语句
            vector<int>tmp;
            tmp.push_back(a);
            tmp.push_back(b);
            tmp.push_back(c);
            p2.push_back(tmp);
        }
    }
    for (int i = 0; i < p2.size(); i++) {//扫描语句数组
        if (p2[i][2] != 1)//非法语句
            cout << "da pian zi" << endl;
        else if (p2[i][2] = 1 && find(p1, p2[i][0]) == find(p1, p2[i][1]))//c为1说明不是非法语句 若a b都通过find函数找到同一个根 说明两者在同一个team
            cout << "we are a team" << endl;
        else
            cout << "we are not a team" << endl;
    }
}