(C卷,100分)- We Are A Team（Java & JS & 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’

输入描述

第一行包含两个整数 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
说明	无

题目解析

本题可以使用并查集建立 a,b 的关联关系。

关于并查集的知识，请看

其余逻辑，按照题目描述写就行，具体可以看代码注释。

2023.09.19

本题c == 1判断a,b是否处于一个团队时，本题判断范围存在歧义，当前有两种思路：

1、仅限判断前面行中建立的关系中，a,b是否处于同一团队

2、不限于前面行，而是等所有行输入完后，才判断a,b是否处于同一团队

下面对这两种思路都进行实现下，代码上差别不大，考试时可以都试下

c==1时仅在当前行前面建立的关系中，判断a,b是否处于同一团队

JS算法源码

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

void (async function () {
  const [n, m] = (await readline()).split(" ").map(Number);

  const msgs = [];
  for (let i = 0; i < m; i++) {
    msgs.push((await readline()).split(" ").map(Number));
  }

  getResult(msgs, n, m);
})();

function getResult(msgs, n, m) {
  // 如果第一行 n 和 m 的值超出约定的范围时，输出字符串”Null“。
  // 1<=n,m<100000
  if (n < 1 || n >= 100000 || m < 1 || m >= 100000) return console.log("NULL");

  const ufs = new UnionFindSet(n + 1);

  msgs.forEach((msg) => {
    const [a, b, c] = msg;

    if (a < 1 || a > n || b < 1 || b > n) {
      // 当前行 a 或 b 的标号小于 1 或者大于 n 时，输出字符串‘da pian zi‘
      return console.log("da pian zi");
    }

    if (c === 0) {
      // c == 0 代表 a 和 b 在一个团队内
      ufs.union(a, b);
    } else if (c === 1) {
      // c == 1 代表需要判定 a 和 b 的关系，如果 a 和 b 是一个团队，输出一行’we are a team’,如果不是，输出一行’we are not a team’
      console.log(
        ufs.find(a) === ufs.find(b) ? "we are a team" : "we are not a team"
      );
    } else {
      // c 为其他值，输出字符串‘da pian zi‘
      console.log("da pian zi");
    }
  });
}

// 并查集实现
class UnionFindSet {
  constructor(n) {
    this.fa = new Array(n).fill(0).map((_, idx) => idx);
  }

  find(x) {
    if (this.fa[x] !== x) {
      this.fa[x] = this.find(this.fa[x]);
      return this.fa[x];
    }
    return x;
  }

  union(x, y) {
    let x_fa = this.find(x);
    let y_fa = this.find(y);

    if (x_fa !== y_fa) {
      this.fa[y_fa] = x_fa;
    }
  }
}

Java算法源码

import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);

    int n = sc.nextInt();
    int m = sc.nextInt();

    int[][] msgs = new int[m][3];
    for (int i = 0; i < m; i++) {
      msgs[i][0] = sc.nextInt();
      msgs[i][1] = sc.nextInt();
      msgs[i][2] = sc.nextInt();
    }

    getResult(msgs, n, m);
  }

  public static void getResult(int[][] msgs, int n, int m) {
    // 如果第一行 n 和 m 的值超出约定的范围时，输出字符串”Null“。
    // 1<=n,m<100000
    if (n < 1 || n >= 100000 || m < 1 || m >= 100000) {
      System.out.println("NULL");
      return;
    }

    UnionFindSet ufs = new UnionFindSet(n + 1);

    for (int[] msg : msgs) {
      int a = msg[0], b = msg[1], c = msg[2];

      if (a < 1 || a > n || b < 1 || b > n) {
        // 当前行 a 或 b 的标号小于 1 或者大于 n 时，输出字符串‘da pian zi‘
        System.out.println("da pian zi");
        continue;
      }

      if (c == 0) {
        // c == 0 代表 a 和 b 在一个团队内
        ufs.union(a, b);
      } else if (c == 1) {
        // c == 1 代表需要判定 a 和 b 的关系，如果 a 和 b 是一个团队，输出一行’we are a team’,如果不是，输出一行’we are not a team’
        System.out.println(ufs.find(a) == ufs.find(b) ? "we are a team" : "we are not a team");
      } else {
        // c 为其他值，输出字符串‘da pian zi‘
        System.out.println("da pian zi");
      }
    }
  }
}

// 并查集实现
class UnionFindSet {
  int[] fa;

  public UnionFindSet(int n) {
    this.fa = new int[n];
    for (int i = 0; i < n; i++) fa[i] = i;
  }

  public int find(int x) {
    if (this.fa[x] != x) {
      return this.fa[x] = this.find(this.fa[x]);
    }
    return x;
  }

  public void union(int x, int y) {
    int x_fa = this.find(x);
    int y_fa = this.find(y);

    if (x_fa != y_fa) {
      this.fa[y_fa] = x_fa;
    }
  }
}

Python算法源码

# 输入获取
n, m = map(int, input().split())
msgs = [list(map(int, input().split())) for _ in range(m)]


# 并查集实现
class UnionFindSet:
    def __init__(self, n):
        self.fa = [i for i in range(n)]

    def find(self, x):
        if self.fa[x] != x:
            self.fa[x] = self.find(self.fa[x])
            return self.fa[x]
        return x

    def union(self, x, y):
        x_fa = self.find(x)
        y_fa = self.find(y)

        if x_fa != y_fa:
            self.fa[y_fa] = x_fa


# 算法入口
def getResult():
    # 如果第一行 n 和 m 的值超出约定的范围时，输出字符串”Null“。
    # 1<=n,m<100000
    if n < 1 or n >= 100000 or m < 1 or m >= 100000:
        print("NULL")
        return

    ufs = UnionFindSet(n + 1)

    for a, b, c in msgs:
        if a < 1 or a > n or b < 1 or b > n:
            # 当前行 a 或 b 的标号小于 1 或者大于 n 时，输出字符串‘da pian zi‘
            print("da pian zi")
            continue

        if c == 0:
            # c == 0 代表 a 和 b 在一个团队内
            ufs.union(a, b)
        elif c == 1:
            # c == 1 代表需要判定 a 和 b 的关系，如果 a 和 b 是一个团队，输出一行’we are a team’,如果不是，输出一行’we are not a team’
            print("we are a team" if ufs.find(a) == ufs.find(b) else "we are not a team")
        else:
            # c 为其他值，输出字符串‘da pian zi‘
            print("da pian zi")


# 算法调用
getResult()

C算法源码

#include <stdio.h>
#include <stdlib.h>

/** 并查集定义 **/
typedef struct {
    int *fa;
    int count;
} UFS;

UFS *new_UFS(int n) {
    UFS *ufs = (UFS *) malloc(sizeof(UFS));

    ufs->fa = (int *) malloc(sizeof(int) * n);
    for (int i = 0; i < n; i++) {
        ufs->fa[i] = i;
    }

    ufs->count = n;

    return ufs;
}

int find_UFS(UFS *ufs, int x) {
    if (x != ufs->fa[x]) {
        ufs->fa[x] = find_UFS(ufs, ufs->fa[x]);
        return ufs->fa[x];
    }
    return x;
}

void union_UFS(UFS *ufs, int x, int y) {
    int x_fa = find_UFS(ufs, x);
    int y_fa = find_UFS(ufs, y);

    if (x_fa != y_fa) {
        ufs->fa[y_fa] = x_fa;
        ufs->count--;
    }
}

int main() {
    int n, m;
    scanf("%d %d", &n, &m);

    int msgs[m][3];
    for (int i = 0; i < m; i++) {
        scanf("%d %d %d", &msgs[i][0], &msgs[i][1], &msgs[i][2]);
    }

    // 如果第一行 n 和 m 的值超出约定的范围时，输出字符串”Null“。
    // 1<=n,m<100000
    if (n < 1 || n >= 100000 || m < 1 || m >= 100000) {
        puts("NULL");
        return 0;
    }

    UFS *ufs = new_UFS(n + 1);

    for (int i = 0; i < m; i++) {
        int a = msgs[i][0], b = msgs[i][1], c = msgs[i][2];

        if(a < 1 || a > n || b < 1 || b > n) {
            // 当前行 a 或 b 的标号小于 1 或者大于 n 时，输出字符串‘da pian zi‘
            puts("da pian zi");
            continue;
        }

        if(c == 0) {
            // c == 0 代表 a 和 b 在一个团队内
            union_UFS(ufs, a, b);
        } else if(c == 1) {
            // c == 1 代表需要判定 a 和 b 的关系，如果 a 和 b 是一个团队，输出一行’we are a team’,如果不是，输出一行’we are not a team’
            puts(find_UFS(ufs, a) == find_UFS(ufs, b) ? "we are a team" : "we are not a team");
        } else {
            // c 为其他值，输出字符串‘da pian zi‘
            puts("da pian zi");
        }
    }

    return 0;
}

c==1时等所有行建立的关系都完成后，再判断a,b是否处于同一团队

JS算法源码

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

void (async function () {
  const [n, m] = (await readline()).split(" ").map(Number);

  const msgs = [];
  for (let i = 0; i < m; i++) {
    msgs.push((await readline()).split(" ").map(Number));
  }

  getResult(msgs, n, m);
})();

function getResult(msgs, n, m) {
  // 如果第一行 n 和 m 的值超出约定的范围时，输出字符串”Null“。
  // 1<=n,m<100000
  if (n < 1 || n >= 100000 || m < 1 || m >= 100000) return console.log("NULL");

  const ufs = new UnionFindSet(n + 1);

  // 过滤出 c == 0 的，且非异常的行，提前构建出所有关系
  msgs
    .filter(([a, b, c]) => c == 0 && a >= 1 && a <= n && b >= 1 && b <= n)
    .forEach(([a, b]) => ufs.union(a, b));

  // 处理 c 不为0的其他情况
  msgs.forEach((msg) => {
    const [a, b, c] = msg;

    if (a < 1 || a > n || b < 1 || b > n) {
      // 当前行 a 或 b 的标号小于 1 或者大于 n 时，输出字符串‘da pian zi‘
      return console.log("da pian zi");
    }

    if (c === 0) {
    } else if (c === 1) {
      // c == 1 代表需要判定 a 和 b 的关系，如果 a 和 b 是一个团队，输出一行’we are a team’,如果不是，输出一行’we are not a team’
      console.log(
        ufs.find(a) === ufs.find(b) ? "we are a team" : "we are not a team"
      );
    } else {
      // c 为其他值，输出字符串‘da pian zi‘
      console.log("da pian zi");
    }
  });
}

// 并查集实现
class UnionFindSet {
  constructor(n) {
    this.fa = new Array(n).fill(0).map((_, idx) => idx);
  }

  find(x) {
    if (this.fa[x] !== x) {
      this.fa[x] = this.find(this.fa[x]);
      return this.fa[x];
    }
    return x;
  }

  union(x, y) {
    let x_fa = this.find(x);
    let y_fa = this.find(y);

    if (x_fa !== y_fa) {
      this.fa[y_fa] = x_fa;
    }
  }
}

Java算法源码

import java.util.Arrays;
import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);

    int n = sc.nextInt();
    int m = sc.nextInt();

    int[][] msgs = new int[m][3];
    for (int i = 0; i < m; i++) {
      msgs[i][0] = sc.nextInt();
      msgs[i][1] = sc.nextInt();
      msgs[i][2] = sc.nextInt();
    }

    getResult(msgs, n, m);
  }

  public static void getResult(int[][] msgs, int n, int m) {
    // 如果第一行 n 和 m 的值超出约定的范围时，输出字符串”Null“。
    // 1<=n,m<100000
    if (n < 1 || n >= 100000 || m < 1 || m >= 100000) {
      System.out.println("NULL");
      return;
    }

    UnionFindSet ufs = new UnionFindSet(n + 1);

    // 过滤出 c == 0 的，且非异常的行，提前构建出所有关系
    Arrays.stream(msgs)
        .filter(msg -> msg[2] == 0 && msg[0] >= 1 && msg[0] <= n && msg[1] >= 1 && msg[1] <= n)
        .forEach(msg -> ufs.union(msg[0], msg[1]));

    // 处理 c 不为0的其他情况
    for (int[] msg : msgs) {
      int a = msg[0], b = msg[1], c = msg[2];

      if (a < 1 || a > n || b < 1 || b > n) {
        // 当前行 a 或 b 的标号小于 1 或者大于 n 时，输出字符串‘da pian zi‘
        System.out.println("da pian zi");
        continue;
      }

      if (c == 0) {
      } else if (c == 1) {
        // c == 1 代表需要判定 a 和 b 的关系，如果 a 和 b 是一个团队，输出一行’we are a team’,如果不是，输出一行’we are not a team’
        System.out.println(ufs.find(a) == ufs.find(b) ? "we are a team" : "we are not a team");
      } else {
        // c 为其他值，输出字符串‘da pian zi‘
        System.out.println("da pian zi");
      }
    }
  }
}

// 并查集实现
class UnionFindSet {
  int[] fa;

  public UnionFindSet(int n) {
    this.fa = new int[n];
    for (int i = 0; i < n; i++) fa[i] = i;
  }

  public int find(int x) {
    if (this.fa[x] != x) {
      return this.fa[x] = this.find(this.fa[x]);
    }
    return x;
  }

  public void union(int x, int y) {
    int x_fa = this.find(x);
    int y_fa = this.find(y);

    if (x_fa != y_fa) {
      this.fa[y_fa] = x_fa;
    }
  }
}

Python算法源码

# 输入获取
n, m = map(int, input().split())
msgs = [list(map(int, input().split())) for _ in range(m)]


# 并查集实现
class UnionFindSet:
    def __init__(self, n):
        self.fa = [i for i in range(n)]

    def find(self, x):
        if self.fa[x] != x:
            self.fa[x] = self.find(self.fa[x])
            return self.fa[x]
        return x

    def union(self, x, y):
        x_fa = self.find(x)
        y_fa = self.find(y)

        if x_fa != y_fa:
            self.fa[y_fa] = x_fa


# 算法入口
def getResult():
    # 如果第一行 n 和 m 的值超出约定的范围时，输出字符串”Null“。
    # 1<=n,m<100000
    if n < 1 or n >= 100000 or m < 1 or m >= 100000:
        print("NULL")
        return

    ufs = UnionFindSet(n + 1)

    for a, b, c in filter(lambda msg: msg[2] == 0 and 1 <= msg[0] <= n and 1 <= msg[1] <= n, msgs):
        ufs.union(a, b)

    for a, b, c in msgs:
        if a < 1 or a > n or b < 1 or b > n:
            # 当前行 a 或 b 的标号小于 1 或者大于 n 时，输出字符串‘da pian zi‘
            print("da pian zi")
            continue

        if c == 0:
            pass
        elif c == 1:
            # c == 1 代表需要判定 a 和 b 的关系，如果 a 和 b 是一个团队，输出一行’we are a team’,如果不是，输出一行’we are not a team’
            print("we are a team" if ufs.find(a) == ufs.find(b) else "we are not a team")
        else:
            # c 为其他值，输出字符串‘da pian zi‘
            print("da pian zi")


# 算法调用
getResult()

C算法源码

#include <stdio.h>
#include <stdlib.h>

/** 并查集定义 **/
typedef struct {
    int *fa;
    int count;
} UFS;

UFS *new_UFS(int n) {
    UFS *ufs = (UFS *) malloc(sizeof(UFS));

    ufs->fa = (int *) malloc(sizeof(int) * n);
    for (int i = 0; i < n; i++) {
        ufs->fa[i] = i;
    }

    ufs->count = n;

    return ufs;
}

int find_UFS(UFS *ufs, int x) {
    if (x != ufs->fa[x]) {
        ufs->fa[x] = find_UFS(ufs, ufs->fa[x]);
        return ufs->fa[x];
    }
    return x;
}

void union_UFS(UFS *ufs, int x, int y) {
    int x_fa = find_UFS(ufs, x);
    int y_fa = find_UFS(ufs, y);

    if (x_fa != y_fa) {
        ufs->fa[y_fa] = x_fa;
        ufs->count--;
    }
}

int main() {
    int n, m;
    scanf("%d %d", &n, &m);

    int msgs[m][3];
    for (int i = 0; i < m; i++) {
        scanf("%d %d %d", &msgs[i][0], &msgs[i][1], &msgs[i][2]);
    }

    // 如果第一行 n 和 m 的值超出约定的范围时，输出字符串”Null“。
    // 1<=n,m<100000
    if (n < 1 || n >= 100000 || m < 1 || m >= 100000) {
        puts("NULL");
        return 0;
    }

    UFS *ufs = new_UFS(n + 1);

    // 过滤出 c == 0 的，且非异常的行，提前构建出所有关系
    for (int i = 0; i < m; i++) {
        int a = msgs[i][0], b = msgs[i][1], c = msgs[i][2];

        if (c == 0 && a >= 1 && a <= n && b >= 1 && b <= n) {
            union_UFS(ufs, a, b);
        }
    }

    // 处理 c 不为0的其他情况
    for (int i = 0; i < m; i++) {
        int a = msgs[i][0], b = msgs[i][1], c = msgs[i][2];

        if (a < 1 || a > n || b < 1 || b > n) {
            // 当前行 a 或 b 的标号小于 1 或者大于 n 时，输出字符串‘da pian zi‘
            puts("da pian zi");
            continue;
        }

        if(c == 0) continue;

        if (c == 1) {
            // c == 1 代表需要判定 a 和 b 的关系，如果 a 和 b 是一个团队，输出一行’we are a team’,如果不是，输出一行’we are not a team’
            puts(find_UFS(ufs, a) == find_UFS(ufs, b) ? "we are a team" : "we are not a team");
        } else {
            // c 为其他值，输出字符串‘da pian zi‘
            puts("da pian zi");
        }
    }

    return 0;
}

免责声明：

1、IT资源小站为非营利性网站，全站所有资料仅供网友个人学习使用，禁止商用
2、本站所有文档、视频、书籍等资料均由网友分享，本站只负责收集不承担任何技术及版权问题
3、如本帖侵犯到任何版权问题，请立即告知本站，本站将及时予与删除下载链接并致以最深的歉意
4、本帖部分内容转载自其它媒体，但并不代表本站赞同其观点和对其真实性负责
5、一经注册为本站会员，一律视为同意网站规定，本站管理员及版主有权禁止违规用户
6、其他单位或个人使用、转载或引用本文时必须同时征得该帖子作者和IT资源小站的同意
7、IT资源小站管理员和版主有权不事先通知发贴者而删除本文

3、原文链接：https://moreit.club/?blog=c%e5%8d%b7100%e5%88%86-we-are-a-team%ef%bc%88java-js-python-c%ef%bc%89，转载请注明出处。

2024华为OD机试题库