DFS-分考场

秒速五厘米 2023-07-10 14:29 26阅读 0赞

## 问题描述 ##

n个人参加某项特殊考试。  
　　为了公平，要求任何两个认识的人不能分在同一个考场。  
　　求是少需要分几个考场才能满足条件。

输入格式

第一行，一个整数n(1<n<100)，表示参加考试的人数。  
　　第二行，一个整数m，表示接下来有m行数据  
　　以下m行每行的格式为：两个整数a，b，用空格分开 (1<=a,b<=n) 表示第a个人与第b个人认识。

输出格式

一行一个整数，表示最少分几个考场。

## 样例输入 ##

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

## 样例输出 ##

## 样例输入 ##

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

## 样例输出 ##

import java.util.Arrays;
    import java.util.Scanner;
    
    public class 分考场 {
        
        final static int max=100;
        final static int INF=0X3f3f3f3f;
        static int ans=INF;
        static boolean flag=false;
        static int que[][]=new int[max+5][max+5];
        static boolean vis[][]=new boolean[max+5][max+5];
        static int queMenber[]=new int[max+5];
        static int num=0;//考场数
        static int n,m,a,b;
    
        static void dfs(int p,int num){
        
            if (ans<=num){
        
                return;
            }
            if(p>n){
        //n表示5个人
                if (ans>num)
                    ans=num;
                return;
            }
            for (int i = 1; i <=num ; i++) {
        
                flag=true;
                for (int j = 1; j <=queMenber[j] ; j++) {
        
                    if (vis[p][que[i][j]]){
        
                        flag=false;
                        break;
                    }
                }
                if (flag){
        
                    queMenber[i]++;
                    que[i][queMenber[i]]=p;
                    dfs(p+1,num);
                    queMenber[i]--;//回溯
                    flag=false;//如果之前所有考场都不可以安排，则选择新建一个考场  如果没有这句可能不会新建考场
                }
            }
            if(!flag)//如果之前的考场都无法与p相容，那么p新建一个考场
            {
        
                num++;
                queMenber[num]=1;
                que[num][1]=p;
                dfs(p+1,num);//新建考场之后不用回溯，因为已经没有其他可能，需要回溯的只会出现在有几个已建考场都容纳p时，选择一种最优的
                //eg  5 4    1 3 2 4 2 5 3 4  最优应该为2个考场 即1，2不在一个考场。
            }
        }
        public static void main(String[] args) {
        
            Scanner sc=new Scanner(System.in);
            n=sc.nextInt();
            m=sc.nextInt();
            for (int i = 1; i <=n ; i++) {
        
                Arrays.fill(vis[i],false);
                Arrays.fill(que[i],-1);
            }
            for(int i=0;i<m;i++)
            {
        
                a=sc.nextInt();
                b=sc.nextInt();
                vis[a][b]=true;//邻接矩阵，离散数学，用矩阵记录关系
                vis[b][a]=true;
            }
            dfs(1,0);//开了
            System.out.println(ans);
        }
    }