【蓝桥杯/DFS】分考场 (Java)

这篇具有很好参考价值的文章主要介绍了【蓝桥杯/DFS】分考场 (Java)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

分考场

题目描述

nnn 个人参加某项特殊考试。

为了公平,要求任何两个认识的人不能分在同一个考场。

求是少需要分几个考场才能满足条件。

输入描述

输入格式:

第一行,一个整数 nnn (1≤n≤1001 \leq n \leq 1001n100),表示参加考试的人数。

第二行,一个整数 mmm,表示接下来有 mmm 行数据。

以下 mmm 行每行的格式为:两个整数 a,ba,ba,b,用空格分开 ( 1≤a,b≤n1 \leq a,b \leq n1a,bn )表示第 aaa 个人与第 bbb 个人认识。

输出描述

输出一行一个整数,表示最少分几个考场。

输入输出样例

示例

输入

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模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【AcWing刷题】蓝桥杯专题突破-深度优先搜索-dfs(8)

    目录 写在前面: 题目:1114. 棋盘问题 - AcWing题库 题目描述: 输入格式: 输出格式: 数据范围: 输入样例: 输出样例: 解题思路: 代码: AC !!!!!!!!!! 写在最后: 怎么样才能学好一个算法? 我个人认为,系统性的刷题尤为重要, 所以,为了学好深度优先搜

    2023年04月09日
    浏览(38)
  • 【洛谷刷题】蓝桥杯专题突破-深度优先搜索-dfs(5)

    目录 写在前面: 题目:P2036 [COCI2008-2009#2] PERKET - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 题目描述: 输入格式: 输出格式: 输入样例: 输出样例: 解题思路: 代码: AC !!!!!!!!!! 写在最后: 怎么样才能学好一个算法? 我个人认为,系统性的刷题尤为重要,

    2023年04月13日
    浏览(49)
  • 【洛谷刷题】蓝桥杯专题突破-深度优先搜索-dfs(4)

    目录 写在前面: 题目:P1149 [NOIP2008 提高组] 火柴棒等式 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 题目描述: 输入格式: 输出格式: 输入样例: 输出样例: 解题思路: 代码: AC !!!!!!!!!! 写在最后: 怎么样才能学好一个算法? 我个人认为,系统性的刷题尤

    2023年04月08日
    浏览(45)
  • 【洛谷刷题】蓝桥杯专题突破-深度优先搜索-dfs(1)

    目录 写在前面: 题目:P1036 [NOIP2002 普及组] 选数 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 题目描述: 输入格式: 输出格式: 输入样例: 输出样例: 解题思路: 代码: AC !!!!!!!!!! 写在最后: 怎么样才能学好一个算法? 我个人认为,系统性的刷题尤为重要

    2024年01月23日
    浏览(39)
  • 172.【华为OD机试】围棋的气(深度优先搜索DFS实现Java&Python&C++&&JS)

    🚀你的旅程将在这里启航!本专栏所有题目均包含优质解题思路,高质量解题代码,详细代码讲解,助你深入学习,深度掌握!

    2024年03月22日
    浏览(73)
  • 深度优先搜索(DFS)算法

    目录 算法思想 时间复杂度和空间复杂度 算法实现 算法优缺点 应用领域 深度优先搜索(DFS)算法的思想是从图的某个起始顶点开始,沿着一条路径尽可能深入地访问图中的所有顶点,直到不能继续为止,然后返回并探索其他路径。具体而言,DFS算法使用栈数据结构来实现,

    2024年02月05日
    浏览(45)
  • 269.【华为OD机试真题】解密犯罪时间(深度优先搜索(DFS)-Java&Python&C++&JS实现)

    🚀点击这里可直接跳转到本专栏,可查阅顶置最新的华为OD机试宝典~ 本专栏所有题目均包含优质解题思路,高质量解题代码(JavaPythonC++JS分别实现),详细代码讲解,助你深入学习,深度掌握!

    2024年02月21日
    浏览(39)
  • 【算法详解 | DFS算法】深度优先搜索解走迷宫问题 | 深度优先图遍历

    by.Qin3Yu 本文需要读者掌握 结构体 和 栈 的操作基础,完整代码将在文章末尾展示。 特别声明:本文为了尽可能使用简单描述,以求简单明了,可能部分专有名词定义不准确。 栈相关操作可以参考我的往期博文: 【C++数据结构 | 栈速通】使用栈完成十进制数转二四八进制数

    2024年02月03日
    浏览(49)
  • 深度优先搜索(DFS)(算法笔记)

    本文内容基于《算法笔记》和官方配套练题网站“晴问算法”,是我作为小白的学习记录,如有错误还请体谅,可以留下您的宝贵意见,不胜感激。 深度优先搜索是一种枚举所有完整路径以遍历所有情况的搜索方法,总是以“深度”作为前进的。实现方式是有很多,最

    2024年02月08日
    浏览(50)
  • [算法日志]图论: 深度优先搜索(DFS)

    ​ 深度优先搜索算法是一种遍历图这种数据结构的算法策略,其中心思想是朝图节点的一个方向不断跳转,当该节点无下一个节点或所有方向都遍历完时,便回溯朝上一个节点的另一个方向继续遍历。这种搜索策略与回溯法有异曲同工之妙。 正因为和回溯法有相似之处,所

    2024年02月03日
    浏览(62)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包