首页 > 试题广场 >

幼儿园分班

[编程题]幼儿园分班
  • 热度指数：2882 时间限制：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。
算法知识视频讲解
添加回答
黄河滴滴66头像 黄河滴滴66 
package com.hhdd.offer.xiaohongshu;

import java.util.HashSet;
import java.util.Scanner;

public class KindeGarten {


    public static int isSuccess(boolean[][] help){
        //set用来代表班级
        HashSet<Integer> set1 = new HashSet<>();
        HashSet<Integer> set2 = new HashSet<>();
        //遍历help二维数组，可以顺序的取出排斥信息
        for(int i = 1;i<help.length;i++){
            for(int j = 1;j<help.length;j++){
                if(help[i][j]){
                    //如果两个班级都没有i同学，则加入1班;j放入2班
                    if(!set1.contains(i)&&!set2.contains(i)){
                        set1.add(i);
                        set2.add(j);
                    }else if(set1.contains(i)){//如果1班含有了i同学，判断1班是否含有j同学
                        if(set1.contains(j)){
                            return 0;
                        }else {
                            set2.add(j);
                        }
                    }else if(set2.contains(i)){//如果2班含有了i同学，判断2班是否含有j同学
                        if(set2.contains(j)){
                            return 0;
                        }else {
                            set1.add(j);
                        }
                    }else {
                        return 0;
                    }
                }
            }
        }
        return 1;
    }


    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int peopleNum = scanner.nextInt();
        int loopNum = scanner.nextInt();
        //set用来代表班级
        HashSet<Integer> set1 = new HashSet<>();
        HashSet<Integer> set2 = new HashSet<>();
        //help二维数组用来存放i同学排斥j同学的信息
        boolean[][] help = new boolean[peopleNum + 1][peopleNum + 1];
        for (int i = 0; i < loopNum; i++) {
            int row = scanner.nextInt();
            int col = scanner.nextInt();
            help[row][col] = true;
        }
        int ans = isSuccess(help);
        System.out.println(ans);


    }

}

发表于 2019-09-01 21:54:10 回复(3)
哼哼哈哈呵呵头像 哼哼哈哈呵呵 
#include<iostream>
#include<stdio.h>
#include<algorithm>
using namespace std;
int n,m,book[500100],flag;
vector<int>arr[500100];
void dfs(int f,int x,int category)
{
    int ne = (category == 1)?2:1;
    book[x] = category;
    for(int i=0;i<arr[x].size();i++)
    {
        if(arr[x][i]!=f)
        {
            if(book[arr[x][i]]==0)
            {
                dfs(x,arr[x][i],ne);
            }
            else if(book[arr[x][i]]!=ne)
            {
                flag = 1;
                break;
            }
                 
        }
    }
}
int main()
{
    cin>>n;
    cin>>m;
    for(int i=1;i<=m;i++)
    {
        int a,b;
        cin>>a>>b;
        arr[a].push_back(b);
        arr[b].push_back(a);
    }
    for(int i=1;i<=n;i++)
    {
        if(!book[i])
            dfs(0,i,1);
    }
    if(flag)
        cout<<0<<endl;
    else
        cout<<1<<endl;
    return 0;
}
二分染色问题 直接dfs 搞什么花里胡哨
发表于 2019-08-20 15:33:27 回复(1)
C/C++
infiniteft头像 infiniteft
用两个map 模拟分班过程，不花哨 
#include <iostream>
#include <map>

#define INIT() ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

using namespace std;
int main()
{
    int n = 0;
    int k = 0;
    INIT();
    cin >> n >> k;
    map<int, bool> cls1, cls2;
    for(int i = 0; i < k; i++)
    {
        int stu1, stu2;
        cin >> stu1 >> stu2;
        if((cls1[stu1] && cls1[stu2]) ||(cls2[stu1] && cls2[stu2]))
        {
            cout << 0 << endl;
            return 0;
        }
        if(cls1[stu1] && !cls2[stu2])
            cls2[stu2] = true;
        else if(cls2[stu1] && !cls1[stu2])
            cls1[stu2] = true;
        else 
        {
            cls1[stu1] = true;
            cls2[stu2] = true;
        }
    }
    cout << 1 << endl;
    return 0;

}


编辑于 2020-04-25 00:47:36 回复(1)
牛客192765642号头像 牛客192765642号
将输入的两个人，分在不同的班，然后看被分的班有没有人讨厌他们，没有就分进去，有两种分法。进1班或者进2班。分进去之后，令讨厌的人赋值为一，表示这个人不能来这个班，。
#include<cstdio>
(802)#include<cstring>
using namespace std;
int main()
{
	int first[10000]={0},second[10000]={0},n,m;//两个班被讨厌的人赋值为一； 
	scanf("%d%d",&m,&n);
	for(int i=0;i<n;i++)
	{
		int a,b;
		scanf("%d %d",&a,&b);
		if(first[a]==0&&second[b]==0)//a，b所在的班级没人讨厌他们 
		{
			first[b]=1;//a进1班，b被讨厌，不能进
			second[a]=1;
		}
        else if(first[b]==0&&second[a]==0)
        {
            first[a]=1;//a进2班
            second[b]=1;
        }
		else
		{
			printf("0\n");
			return 0;
		}
	}
	printf("1\n");
	return 0;
}

发表于 2020-04-01 15:54:15 回复(1)
C/C++
nbgao头像 nbgao 
#include <bits/stdc++.h>
using namespace std;

int main(){
    int n,m,x,y;
    cin>>n>>m;
    bool a[n+1],b[n+1];
    memset(a,false,sizeof(a));
    memset(b,false,sizeof(b));
    for(int i=0;i<m;i++){
        cin>>x>>y;
        if(!a[x] && !b[y] && !a[y] && !b[x]){
            a[x] = b[y] = true;
        }else if(b[x] && !a[y])
            a[y] = true;
        else if(a[x] && !b[y])
            b[y] = true;
    }
    bool flag =  true;
    for(int i=1;i<=n;i++)
        if(a[i]==b[i] && a[i])
            flag = false;
    cout<<(flag?1:0)<<endl;
    return 0;
}

发表于 2019-10-12 12:49:12 回复(0)
ElonB头像 ElonB 
"""
深度优先搜索+条件判断
"""
import sys


def dfs(group, a, step):
    if step == len(a):
        return True
    ret = False
    if group[a[step][0]] == 0 and group[a[step][1]] == 0:
        group[a[step][0]] = 1
        group[a[step][1]] = -1
        ret = dfs(group, a, step + 1)
        group[a[step][0]] = -1
        group[a[step][1]] = 1
        ret = ret or dfs(group, a, step + 1)
    elif group[a[step][0]] == 0:
        group[a[step][0]] = -group[a[step][1]]
        ret = dfs(group, a, step + 1)
    elif group[a[step][1]] == 0:
        group[a[step][1]] = -group[a[step][0]]
        ret = dfs(group, a, step + 1)
    elif group[a[step][0]] * group[a[step][1]] == -1:
        ret = dfs(group, a, step + 1)
    else:
        ret = False
    return ret


if __name__ == '__main__':
    # sys.stdin = open("input.txt", "r")
    n = int(input())
    m = int(input())
    a = []
    for _ in range(m):
        a.append(list(map(int, input().strip().split())))
    group = [0] * (n + 1)
    ans = dfs(group, a, 0)
    print(1 if ans else 0)

发表于 2019-10-06 16:49:47 回复(0)
C/C++
今天也要乖头像 今天也要乖
#include <iostream>
#include <vector>
#include <unordered_set>
#include <set>
using namespace std;
bool help(vector<vector<int>> &data, int n);
int main(){
    int m = 0;
    cin >> m;
    int n = 0;
    cin >> n;
    
    vector<vector<int>> data(n, vector<int>(2, 0));
    for(int i = 0;i<n;i++){
        cin >> data[i][0] >> data[i][1];
    }
    bool res = help(data, n);
    if(res)
        cout << 1;
    else
        cout << 0;
    return 0;
}
bool help(vector<vector<int>> &data, int n){
    if(n <= 1)
        return true;
    unordered_set<int> s0;
    unordered_set<int> s1;
    s0.insert(data[0][0]);
    s1.insert(data[0][1]);
    for(int i = 1;i<n;i++){
        int d0 = data[i][0];
        int d1 = data[i][1];
        if(s0.find(d0) == s0.end() && s1.find(d0) == s1.end()){
            if(s0.find(d1)!=s0.end()){
                s1.insert(d0);
            }else if(s1.find(d1) != s1.end()){
                s0.insert(d0);
            }
            else{
                s0.insert(d0);
                s1.insert(d1);
            }
        }else if(s0.find(d0) != s0.end()){
            if(s0.find(d1) != s0.end())
                return false;
            else
                s1.insert(d1);
        }
        else{
            if(s1.find(d1) != s1.end()){
                return false;
            }
            else{
                s0.insert(d1);
            }
        }
    }
    return true;
}
发表于 2019-08-17 08:54:06 回复(0)
繁星似尘头像 繁星似尘
个人的想法比较简单，就是通过把不排斥的分为一组，统计可以分多少个组，如果组的个数大于2，则失败，否则成功。
发表于 2019-07-13 11:07:59 回复(1)
大涵菜头像 大涵菜

#八皇后算法思想
n = int(input())#小朋友个数
m = int(input())#要求数目
mat = [[0]*(n) for i in range(n)]
for i in range(m):
res = [int(j) for j in input().split()]
mat[res[0]-1][res[1]-1]=1
mat[res[1]-1][res[0]-1]=1

#定义判断第index个同学所处第color个班级是否去前index个同学相矛盾
def check(state,index,color):
for i in range(index):
if state[i]==color and mat[i][index]==1:
return False
return True
def fenban(state,index):
if index==n:
return 1
for color in (0,1):
if check(state,index,color):
state[index]= color
if fenban(state,index+1)==1:
return 1
return 0
state=[0]*n#学生分配的班级
print(fenban(state,0))

发表于 2019-05-19 20:57:36 回复(0)
Python
月亮上的熊猫头像 月亮上的熊猫
思路：找规律后暴力。
所有的数据输入后，互斥的两个小朋友为a，b。
假设，新分的两个班为x，y。
逐个读取互斥的两个小朋友，有以下几种情况：
（1） a，b已在同一个班内，无法分班，返回0
（2）a，b都不在任何一个班内，把a加入x班，b加入y班
（3）a在x班，但b不在同一个班内，把a加入x班，b加入y班
接下来的（4）（5）（6）同理可得。
如果处理完了所有互斥请求，则分班完成，返回1 
n = int(input())
q = int(input())
a = []
b = []
for i in range(q):
    ai,bi = list(map(int,input().split()))
    a.append(ai)
    b.append(bi)
    
x = []
y = []
for i in range(q):
    if (a[i] in x and b[i] in x) or (a[i] in y and b[i] in y):
        print(0)
        exit()
    elif a[i] not in x and a[i] not in y and b[i] not in x and b[i] not in y:
        x.append(a[i])
        y.append(b[i])
    elif a[i] in x and b[i] not in x:
        x.append(a[i])
        y.append(b[i])
    elif b[i] in x and a[i] not in x:
        x.append(b[i])
        y.append(a[i])
    elif a[i] in y and b[i] not in y:
        y.append(a[i])
        x.append(b[i])
    elif b[i] in y and a[i] not in y:
        y.append(b[i])
        x.append(a[i])
print(1)
编辑于 2019-08-21 21:55:51 回复(2)
C/C++
昔遥暮云头像 昔遥暮云 
#include <bits/stdc++.h>
using namespace std;
int main(){
    set<int> arr1,arr2;
    int n,k,flag=1;
    cin>>n>>k;
    for(int i=0;i<k;i++){
        int a,b;
        cin>>a>>b;
        if(arr1.find(a)==arr1.end()&&arr2.find(a)==arr2.end()){
            arr1.insert(a);
            arr2.insert(b);
        }
        else if(arr1.find(a)!=arr1.end()){
            if(arr1.find(b)==arr1.end())
                arr2.insert(b);
            else{
                flag=0;
                break;
            }
        }
        else if(arr2.find(a)!=arr2.end()){
            if(arr2.find(b)==arr2.end())
                arr1.insert(b);
            else{
                flag=0;
                break;
            }
        }
    }
    cout<<flag;
    return 0;
}

发表于 2019-10-21 16:01:04 回复(0)
喵喵喵喵喵喵喵喵喵喵喵喵喵喵头像 喵喵喵喵喵喵喵喵喵喵喵喵喵喵 
def main():
    n = int(input())
    request_n = int(input())

    x = []
    y = []
    for i in range(request_n):
        req = input().split()
        req = [int(r) for r in req]
        if req[0] not in x and req[0] not in y:
            x.append(req[0])
            y.append(req[1])
            continue
        
        if req[0] in x and req[1] in x:
            print(0)
            return
        elif req[0] in y and req[1] in y:
            print(0)
            return
        elif req[0] in x and req[1] not in y:
            y.append(req[1])
        elif req[0] in y and req[1] not in x:
            x.append(req[1])
    print(1)
    return

if __name__ == "__main__":
    main()

思路：将互斥的小朋友分在不同班级内，若能分开，则返回１，否则返回０
发表于 2023-07-19 10:43:53 回复(0)
牛客587294869号头像 牛客587294869号 
import java.util.HashSet;
import java.util.Scanner;
public class Main{
    public static void main(String[] args) {
        
        Scanner scanner = new Scanner(System.in);
        int stdNum = scanner.nextInt();
        scanner.nextLine();
        int requNum = scanner.nextInt();
        scanner.nextLine();

        HashSet<Object> left = new HashSet<>();
        HashSet<Object> right = new HashSet<>();

        boolean isOk = true;
        for (int i=0;i<requNum;i++){
            int l = scanner.nextInt();
            int r = scanner.nextInt();
            if (left.contains(l) && !right.contains(r) && !left.contains(r)){
                right.add(r);
                scanner.nextLine();
                continue;
            }
            if (right.contains(l) && !right.contains(r) && !left.contains(r)){
                left.add(r);
                scanner.nextLine();
                continue;
            }
            if (left.contains(l) && left.contains(r) || right.contains(l) && right.contains(r)){
                System.out.println(0);
                isOk=false;
                break;
            }

            left.add(l);
            right.add(r);
            scanner.nextLine();
        }
        if(isOk){
            System.out.println(1);
        }
    }
}

发表于 2022-06-27 21:17:03 回复(0)
牛客587501400号头像 牛客587501400号 
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace TestMachine
{
    public static class T01_FenBan
    {
        public class Request
        {
            public int num;
            public int notlike;
        }
        public static void Main()
        {
            string input = Console.ReadLine();
            int max = int.Parse(input);
            input = Console.ReadLine();
            int RequsetCount = int.Parse(input);
            List<int> Clase1 = new List<int>();
            List<int> Clase2 = new List<int>();
            List<Request> AllRequest = new List<Request>();
            for (int i = 0; i < RequsetCount; i++)
            {
                input = Console.ReadLine();
                string[] inputs = input.Split(' ');
                int num = int.Parse(inputs[0]);
                int notlike = int.Parse(inputs[1]);
                AllRequest.Add(new Request() { num = num, notlike = notlike });
            }
            int answer = DealRequest(AllRequest,Clase1,Clase2,0)?1:0;
            Console.WriteLine(answer);
        }
        private static bool DealRequest(List<Request> allrequest, List<int> class1, List<int> class2, int i)
        {
            bool answer = true;
            if (i == allrequest.Count)
            {
                return true;
            }
            Request _request = allrequest[i];
            if (class1.Count == 0 || class2.Count == 0)
            {
                class1.Add(_request.num);
                class2.Add(_request.notlike);
                answer = DealRequest(allrequest, class1, class2, ++i);
            }
            else if ((class1.Exists(t => t == _request.num) && class1.Exists(t => t == _request.notlike)) || (class2.Exists(t => t == _request.num) && class2.Exists(t => t == _request.notlike)))
            {
                return false;
            }
            else if ((class1.Exists(t => t == _request.num) && class2.Exists(t => t == _request.notlike))||(class2.Exists(t => t == _request.num) && class1.Exists(t => t == _request.notlike)))
            {
                answer = DealRequest(allrequest, class1, class2, ++i);
            }
            else if (class1.Exists(t => t == _request.num) && !class2.Exists(t => t == _request.notlike))
            {
                class2.Add(_request.notlike);
                answer = DealRequest(allrequest, class1, class2, ++i);
            }
            else if (class2.Exists(t => t == _request.num) && !class1.Exists(t => t == _request.notlike))
            {
                class1.Add(_request.notlike);
                answer = DealRequest(allrequest, class1, class2, ++i);
            }
            else if (!class2.Exists(t => t == _request.num) && !class1.Exists(t => t == _request.notlike))
            {
                List<int> temp1 = CopyList(class1);
                List<int> temp2 = CopyList(class2);
                temp1.Add(_request.num);
                temp2.Add(_request.notlike);
                bool tempanswer = DealRequest(allrequest, temp1, temp2, ++i);
                if (!tempanswer)
                {
                    temp1 = CopyList(class1);
                    temp2 = CopyList(class2);
                    temp2.Add(_request.num);
                    temp1.Add(_request.notlike);
                    tempanswer = DealRequest(allrequest, temp1, temp2, ++i);
                }
                else return true;
                if (!tempanswer) return false;
            }
            else if (class2.Exists(t => t == _request.num) && class1.Exists(t => t == _request.notlike))
            {
                answer = false;
            }
            return answer;
        }
        public static List<int> CopyList(List<int> a)
        { 
            List<int> b = new List<int>();
            foreach (int item in a)
            {
                b.Add(item);
            }    
            return b;
        }
    }
}
应该用Switch case写 但是懒得改了
逻辑就是处理每一个请求
根据请求的情况放置人员
难点在于
1 2
3 4
这样的请求，
因为a班有1.b班有2
那么3 和4会用两种放置的方法。
所以代码中采用了迭代的方法。
发表于 2022-03-22 15:30:22 回复(0)
找个工作也太难了头像 找个工作也太难了 
import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int childrenNum=sc.nextInt();
        int queryNum=sc.nextInt();
        HashSet<Integer> class1=new HashSet<>();
        HashSet<Integer> class2=new HashSet<>();
        for(int i=0;i<queryNum;++i){
            int child1=sc.nextInt();
            int child2=sc.nextInt();
            boolean flag11=class1.contains(child1);
            boolean flag12=class1.contains(child2);
            boolean flag21=class2.contains(child1);
            boolean flag22=class2.contains(child2);
            if((flag11 && flag12)||(flag21 && flag22)){
                System.out.println(0);
                return;
            }else if(flag11 && !flag22){
                class2.add(child2);
            }else if(flag12 && !flag21){
                class2.add(child1);
            }else if(flag21 && !flag12){
                class1.add(child2);
            }else if(flag22 && !flag11){
                class1.add(child1);
            }else if(!flag11 && !flag12 && !flag21 && !flag22){
                class1.add(child1);
                class2.add(child2);
            }
        }
        System.out.println(1);
    }
}

发表于 2021-08-09 16:18:49 回复(0)
C/C++
无华，头像 无华，
        采用离散数学的方法，创建A*A的关系矩阵，在矩阵中若1 2排斥则[1][2]=[2][1]=1,其余点初值为0，对矩阵做A次自乘(若A为偶数则为A-1次)，后检查下标为[i][i]的元素(1->A),若存在非零值，则代表无法完成分班，若均为零代表可以完成分班。
        对关系矩阵做 i次自乘后的关系矩阵代表任意一节点经过i次移动能到达其他节点的路径条数，在本题中若经过奇数次移动，某节点能返回到自身，则无法将这个奇数回路放进两个班中。 
#include<iostream>

using namespace std;

int main()
{
    int a,b,c,d,e;
    bool This=1;
    cin>>a;
    int *p=new int[a*a];
    int *q=new int[a*a];
    int *r=new int[a*a];
    cin>>b;
    for(int i=0;i<a;i++)
    {
        for(int j=0;j<a;j++)
        {
            p[(i)*a+(j)]=0;
            r[(i)*a+(j)]=0;
            if(i==j)
            {
                q[(i)*a+(j)]=1;
            }else
            {
                q[(i)*a+(j)]=0;
            }
        }

    }
    for(int i=0;i<b;i++)
    {
        cin>>c>>d;
        p[(c-1)*a+(d-1)]=1;
        p[(d-1)*a+(c-1)]=1;
    }
    e=a;
    if(e%2==0)
    {
        e=e-1;
    }
    for(int m=0;m<e;m++)
    {
        for(int i=0;i<a;i++)
        {
            for(int j=0;j<a;j++)
            {
                for(int k=0;k<a;k++)
                {
                    r[(i)*a+(j)]+=q[(j)*a+(k)]*p[(k)*a+(i)];
                }
            }
        }
        for(int i=0;i<a;i++)
        {
            for(int j=0;j<a;j++)
            {
                q[(i)*a+(j)]= r[(i)*a+(j)];
                r[(i)*a+(j)]=0;
            }
        }
    }

    for(int i=0;i<a;i++)
    {
        if(q[(i)*a+i]!=0)
        {
            This=0;
        }
    }

    cout<<This;
    delete [] r;
    delete [] q;
    delete [] p;
    return 0;
}

发表于 2020-09-18 17:42:29 回复(0)
Java
shasha96头像 shasha96
import java.util.*;
public class Main {
 public static void main(String[] args) {
    Scanner sc=new Scanner(System.in);
    int n=sc.nextInt();//小朋友人数
    int q=sc.nextInt();//请求数量
    List<Integer> list1=new ArrayList<Integer>();//分班1
    List<Integer> list2=new ArrayList<Integer>();//分班1
    int[][] quest=new int[q][3];//多留一列，用来表示这个请求是否已经被处理0，未处理，2，已处理，1经过一次过滤
    for (int i = 0; i <q ; i++) {
      quest[i][0]=sc.nextInt();
      quest[i][1]=sc.nextInt();
    }
    //预处理
    list1.add(quest[0][0]);
    list2.add(quest[0][1]);
    quest[0][2]=1;
    int count=0;
    while(list1.size()+list2.size()<n){
         count++;
         if(count>2*q) break;
        for (int i = 1; i <q ; i++) {
          if(quest[i][2]<=1){
            if(list1.contains(quest[i][0])){
              if(list1.contains(quest[i][1])){
                count=2*q+1;
                break;
              }
              list2.add(quest[i][1]);
              quest[i][2]=2;
            }else if(list1.contains(quest[i][1])){
              if(list1.contains(quest[i][0])){
                count=2*q+1;
                break;
              }
              list2.add(quest[i][0]);
              quest[i][2]=2;
            }else if(list2.contains(quest[i][1])){
              if(list2.contains(quest[i][0])){
                count=2*q+1;
                break;
              }
              list1.add(quest[i][0]);
              quest[i][2]=2;
            } else if(list2.contains(quest[i][0])){
              if(list2.contains(quest[i][1])){
                count=2*q+1;
                break;
              }
              list1.add(quest[i][1]);
              quest[i][2]=2;
            }else if(quest[i][2]==0){
              quest[i][2]=1;
            }else{
              list1.add(quest[i][0]);
              list2.add(quest[i][1]);
            }

        }
      }

    }
    if(count<=2*q)
      System.out.println(1);
    else
      System.out.println(0);
  }
}

发表于 2020-08-30 16:44:12 回复(0)
牛客123037741号头像 牛客123037741号
dfs判断有没有环，如果有环而且环上节点数为奇数那就不行；没有环或者环上节点数为偶数就可以

发表于 2020-08-19 15:37:00 回复(0)
0.068头像 0.068
二分染色问题，dfs求解。前面很多回答用例如用set模拟分班情况虽然能通过，但其实并没有考虑到所有情况。
看到前面的回答，学习了下二分染色问题，参考博客https://blog.csdn.net/abc1235454/article/details/89439526 
public class Test {
    private static int []color;
    private static int [][]G;
    public static void main(String[]args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt()+1;  //节点数目
        int k = sc.nextInt();  //边数
        G = new int[n][n];     //邻接矩阵
        color = new int[n];    //节点颜色，默认没有颜色0，其他两种颜色-1，1
        for(int i = 0; i< k; i++){
            int x = sc.nextInt();
            int y = sc.nextInt();
            G[x][y] = 1;
            G[y][x] = 1;
        }
        //如果是连通图，则一次dfs即可访问所有位置
        //但题目没有说明，故要依次检查各个顶点的情况
        for(int i = 1; i< n; i++){
            if(color[i] == 0){
                if(!dfs(i,1)){
                    System.out.println("0");
                    return;
                }
            }
        }
        System.out.println("1");
    }
    private static boolean dfs(int v, int c){
        color[v] = c;
        for(int j = 1; j< G[v].length; j++){
            //是相邻节点
            if(G[v][j] == 1){
                //相邻点没有染色
                if(color[j] == 0){
                    //给相邻点染色，若相邻点的子结点中存在相邻点同色的情况，则返回false
                     if(dfs(j,-c) == false){
                         return false;
                     }
                }
                //相邻点同色
                if(color[j]==c){
                    return false;
                }
            }
        }
        return true;
    }
}


发表于 2020-07-19 11:05:06 回复(0)
赏口饭吃头像 赏口饭吃 
n=int(input())
k=int(input())
a=[]
for i in range(k):
    a.append(list(map(int,input().split())))
a.sort()
a1=[a[0][0]]
a2=[a[0][1]]
res=[]
#把不能随便分班的先分班，暂时可以随便分的计入到res中
for i in a[1:]:           
    if i[0] in a1 and i[1]not in a2:
        a2.append(i[1])
    elif i[0] in a2 and i[1]not in a1:
        a1.append(i[1])
    elif i[1] in a1 and i[0]not in a2:
        a2.append(i[0])
    elif i[1] in a2 and i[0]not in a1:
        a1.append(i[0])
    elif i[0]not in a1 and i[0]not in a2 and i[1]not in a1 and i[1]not in a2 :
        res.append(i)

temp=[]
#对res中的学生进行分班，知道res中只剩下可以随机分班不影响互斥关系的
while res!=temp:
    temp=res[:]
    for i in res:
        if i[0] in a1 and i[1]not in a2:
            a2.append(i[1])
            res.remove(i)
        elif i[0] in a2 and i[1]not in a1:
            a1.append(i[1])
            res.remove(i)
        elif i[1] in a1 and i[0]not in a2:
            a2.append(i[0])
            res.remove(i)
        elif i[1] in a2 and i[0]not in a1:
            a1.append(i[0])
            res.remove(i)
n=a1+a2
n.sort()
m=list(set(n))
m.sort()
if n!=m:
    print(0)
else:
    print(1)

发表于 2020-06-15 11:05:21 回复(0)
提交观点

问题信息

C++工程师 iOS工程师 安卓工程师 数组 运维工程师 前端工程师 算法工程师 测试工程师 图 PHP工程师 小红书 递归 贪心 模拟 2019 Java工程师
上传者：小小
难度：
29条回答 9324浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号