首页 > 试题广场 >

幼儿园分班

[编程题]幼儿园分班
  • 热度指数:3018 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解
幼儿园一个大班要分成两个小班,有些小朋友不希望自己和其他某几位小朋友同班。园长向大家收集了不希望同班的要求,然后视情况将一个大班的小朋友分成两个班。请你开发一个程序,帮助园长快速判断是否所有小朋友的不同班请求都可以被满足。

输入描述:
输入分为三部分,第一个部分是一个 int,代表这个大班里小朋友的总数。第二部分是一个 int,代表园长采集到的小朋友们的请求数。第三部分是小朋友们的请求,每个请求由两个 int 组成,第一个 int 代表提请求的小朋友,第二个 int 代表他不希望同班的另一位小朋友。


输出描述:
如果所有小朋友的请求都可以被满足,输出 1,否则输出 0。
示例1

输入

5
5
1 2
1 3
1 4
1 5
2 3

输出

0

说明

总共有 5 位小朋友,总共采集到了 5 个请求。分别是:1 不希望和 2 同班。1 不希望和 3 同班。1 不希望和 4 同班。1 不希望和 5 同班。2 不希望和 3 同班。不能满足所有人的请求,输出 0。
示例2

输入

5
4
1 2
1 3
1 4
1 5

输出

1

说明

总共有 5 位小朋友,总共采集到了 4 个请求。分别是:1 不希望和 2 同班。1 不希望和 3 同班。1 不希望和 4 同班。1 不希望和 5 同班。可以满足所有人的请求,分班方式:1 一个人一班,2、3、4、5 另一班。输出 1。
头像 必不可能秃头
发表于 2022-03-15 11:33:11
import java.util.*; public class Main{ public static void main(String[] args) { Scanner sc = new Scanner(System.in); int stu_num 展开全文
头像 啄菜的鸡仔
发表于 2023-01-28 22:07:02
def cls(): m = int(input()) n = int(input()) ls = [] cls1 = [] cls2 = [] for i in range(n): a,b = map(int,input().stri 展开全文
头像 bandiaoz
发表于 2024-12-26 17:41:23
解题思路 这是一道分班问题,主要思路如下: 问题分析: 一个大班要分成两个小班 每个小朋友可能不希望和某些人同班 需要判断是否能满足所有要求 本质是一个二分图染色问题 解决方案: 使用两个数组记录每个小朋友的分班情况 对于每个请求 ,尝试将 分到不同班 如果发现冲突,则无法满足要求 展开全文
头像 笔寞
发表于 2021-08-05 17:15:19
//其实就是判断是不是二分图,直接用染色法就好了 import java.util.*; public class Main{ static int n, m, N = 1000, M = 2 * 1000, idx; static int[] h = new int[N], e 展开全文
头像 牛客732005329号
发表于 2022-08-18 00:07:11
import java.util.*; // 注意类名必须为 Main, 不要有任何 package xxx 信息 public class Main {     public static void main(String[] args) { & 展开全文