本文共 1154 字，大约阅读时间需要 3 分钟。

题目链接:

问题描述

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

输入格式

　　第一行，一个整数n(1<n<100)，表示参加考试的人数。

输出格式

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

样例输入

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

样例输出

4

5

解题思路

数据比较小，直接DFS就行了。在已知的状态下，然后去判断下一个学生是否可以在之前存在的教室，如果不可以的话，那么就新开一个教室。

#include 
   
    #include 
    
     int n, min_kes, p[102][102], map[102][102];void DFS(int x, int kes){    if (kes >= min_kes)        return ;    if (x > n)    {        if (kes < min_kes)            min_kes = kes;        return ;     }    for (int i = 1; i <= kes; i++)    {        int k = 0;        while (p[i][k] && !map[x][p[i][k]])            k++;        if (!p[i][k])        {            p[i][k] = x;            DFS(x + 1, kes);            p[i][k] = 0;        }    }    p[kes + 1][0] = x;    DFS(x + 1, kes + 1);    p[kes + 1][0] = 0;}int main(){    int t, a, b;    scanf("%d%d", &n, &t);    min_kes = n;    while (t--)    {        scanf("%d%d", &a, &b);        map[a][b] = map[b][a] = 1;    }    DFS(1, 0);    printf("%d\n", min_kes);    return 0;}
    
   

转载地址：https://lzyws739307453.blog.csdn.net/article/details/86768576 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！