lanqiao OJ 109 分考场

#include<iostream>
#include<cstring>
#include<algorithm>
 
using namespace std ;
const int N = 110;
int a[N][N] ;
int v[N][N] ; //v表示第i个教室的第j个座位
int n , m ; 
int num = N ;//表示当前的最优教室安排
void dfs(int x,int room){
  if(room >= num ) return ;//比以前的最好情况差，直接返回
  if(x > n ){
    num = min(num , room) ;//其实这里直接num = room 就行  因为前面比sum大的已经返回了
    return ;
  } 
  int k = 1 ;//遍历教师的每一个座位
  for(int j = 1 ; j <= room ; j ++){
    k=1;
    while(v[j][k] && !a[x][v[j][k]]) k ++ ;//往后找 如果中间碰到了一个认识的人k就停止+1
    if(!v[j][k]){                          //如果找完遍历教室的人没有认识的就刚好把它安排在这个教室的k个座位
      v[j][k] = x ;
      dfs(x+1,room);
      v[j][k] = 0 ;
    }
  }
//所有的教室都有认识的，只能给这个人单独开一个教室
  v[room+1][1] =x ;
  dfs(x+1,room+1) ;
  v[room+1][1] = 0 ;
}
 
 
int main(){
  cin >> n >> m ;
  for(int i = 1 ; i <= m ; i ++){
    int x,y ; cin >> x >> y ;
    a[x][y] = a[y][x] = 1 ;
  }
  dfs(1,1);
  cout << num << endl ;
  return 0 ;
}