蓝桥杯真题-分考场

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;

#define maxn 105
int n,m;
int f[maxn][maxn]={0};//f[i][j]=0表示第i个人与第j个人无关系 
int people_room[maxn];//p_c[i]表示第i个人所在的考场 
int ans=99999;

bool judge(int x,int y){//判断第x个人是否可以在第y个考场
    //判断该考场没有与x有关系的人
    for(int i = 1;i<=n;i++){
        if(people_room[i] == y){//表示i是在y考场的人
            if(f[i][x]==1){//表示i与x有关系 
                return false;
            }
        } 
    } 
     return true;
} 

void arrange_room(int x,int room_num){//表示当前安排到第x个人，已使用room_num个数量的考场 
    if(room_num>=ans) {
        return;
    }
    if(x>n) {//表示安排任务结束 
        ans=min(ans,room_num);
        return;
    }
    //枚举所有已使用的考场，看第x个人是否可在
    for(int room=1;room<=room_num;room++){
        if(judge(x,room)==true){
            people_room[x]=room;//涂色（安排房间）
            arrange_room(x+1,room_num);
            people_room[x]=0;
        }
    } 
    //前面room_num所有考场都无法使用，只能新建考场
    people_room[x]=room_num+1;
    arrange_room(x+1,room_num+1);
    people_room[x]=0;
}

int main(){
    int x,y;
    cin>>n>>m;
    while(m--){
        cin>>x>>y;
        f[x][y]=f[y][x]=1;
    }
    arrange_room(1,0);
    cout<<ans<<endl;
}