分考场
题目描述
nnn 个人参加某项特殊考试。
为了公平,要求任何两个认识的人不能分在同一个考场。
求是少需要分几个考场才能满足条件。
输入描述
输入格式:
第一行,一个整数 nnn (1≤n≤1001 \leq n \leq 1001≤n≤100),表示参加考试的人数。
第二行,一个整数 mmm,表示接下来有 mmm 行数据。
以下 mmm 行每行的格式为:两个整数 a,ba,ba,b,用空格分开 ( 1≤a,b≤n1 \leq a,b \leq n1≤a,b≤n )表示第 aaa 个人与第 bbb 个人认识。
输出描述
输出一行一个整数,表示最少分几个考场。
输入输出样例
示例
输入文章来源:https://www.toymoban.com/news/detail-791283.html
5 8 1 2 1 3 1 4 2 3 2 4 2 5 3 4 4 5
copy
输出文章来源地址https://www.toymoban.com/news/detail-791283.html
4
copy
运行限制
- 最大运行时间:1s
- 最大运行内存: 256M
import java.util.Scanner;
public class Main{
static int relationship[][];
static int map[][];//room,person
static int n,m;
static int minroom=110;
static void dfs(int person,int room){
if(room>=minroom){
return;
}
if(person==n){
minroom=room;
return;
}
int i=1;
for (;i<=room;++i){
int k=0;
while(map[i][k]!=0&&relationship[person+1][map[i][k]]==0){
++k;
}
if(map[i][k]==0){
map[i][k]=person+1;
dfs(person+1,room);
map[i][k]=0;
}
}
map[i][0]=person+1;
dfs(person+1,room+1);
map[i][0]=0;
}
public static void solve(){
Scanner scan = new Scanner(System.in);
n=scan.nextInt();
m=scan.nextInt();
minroom=110;
relationship=new int[n+1][n+1];
map=new int[n+1][n+1];
for(int i=0;i<m;++i){
int a,b;
a=scan.nextInt();
b=scan.nextInt();
relationship[a][b]=relationship[b][a]=1;
}
map[1][0]=1;
dfs(1,1);
System.out.println(minroom);
scan.close();
}
public static void main(String[] args) {
solve();
}
}
到了这里,关于【蓝桥杯/DFS】分考场 (Java)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!