蓝桥杯第 12 天 109 国赛第一题 分考场（干了一个小时的题）

注释很全，肯定能看懂！！！！ 

   static final int N = 110;
    static int[][] a = new int[N][N];//关系表
    static int[][] p = new int[N][N];//房间状态
    static int num = N;//考场数量
    static int n,m;
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        m = scan.nextInt();
        for(int i = 1;i<= m;i++) {
            int u = scan.nextInt();
            int v = scan.nextInt();
            a[u][v] = a[v][u] = 1;//互为熟人
        }
        p[1][0] = 1;
        dfs(1, 1);
        System.out.println(num);
        scan.close();
    }
//cnt 为现在的需要占用的教室数
    private static void dfs(int x, int cnt) {
        if(cnt >= num) return;//注意等于也退出，等于找了个寂寞
        if(x == n) {
            num = cnt;
            return;
        }
        
        int j,k;
        for(j = 1;j<=cnt;j++) {//考场遍历，从之前的1-cnt考场开始循环
            k = 0;//考场是j
            while(p[j][k] != 0 && a[x+1][p[j][k]] == 0)k++; //这里是判断第i个考场的第j个学生存在，并且当前学生与第j个学生不认识
           //如果p[j][k] == 0为while的退出条件，因为a[x+1][p[j][k]]必为0
            if(p[j][k] == 0) {
         //这个人是当前考场的第一人   或者这个人与考场上的人都不认识（与之前k-1个人都不是熟人哦，且前面的递归已经证明前k-1个人互不认识）。
            	//因为在这个递归函数之前，a[j][k]中的k已经加过了（从0开始加的，表示教室坐的人）
                p[j][k] = x + 1;//考生可以坐进这个考场了，不用再安排新的考场
                dfs(x + 1, cnt);//递归
                p[j][k] = 0;//回溯
            }
        }
        //之前开辟的考场不满足第x+1个学生，因为a[x+1][p[j][k]] == 0这个条件不满足！！！！
        p[j][0] = x + 1;//新开辟一个考场，让第x + 1个学生坐进去
        dfs(x + 1, cnt + 1);
        p[j][0] = 0;//回溯
    }