Python：分考场（DFS剪枝）

题目描述

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

输出

4

 思路：

        从第1个考场开始，逐个加入考生。每新加进来一个人x，都与已经开设的考场里面的人进行对比，如果认识，就换个考场。直到找到一个考场，考场里面所有的人都不认识x，x就可以坐在这里。如果所有已经开设的考场都有熟人，就开一个新考场给x坐。
        剪枝：用剪枝来减少搜索。在搜索一种新的可能的考场安排时，如果需要的考场数量已经超过了原来某个可行的考场安排，就停止。

参考代码：

def dfs(x,room):
  global num,p
  if room>num: #需要的考场数量超过了原来可行的考场安排，停止
    return
  if x>n:
    if room<num: #用的考场更少了
      num=room  #更新考场数量
    return
  for j in range(1,room+1):
    k=0
    while p[j][k] and a[x][p[j][k]]==0:
      k+=1
    if p[j][k]==0:  # k 座位没人坐
      p[j][k]=x   #第 j 考场的k座位，安排x坐
      dfs(x+1,room) #第x人安排好了，继续安排下一人
      p[j][k]=0   #回溯，放开这个座位
  p[room+1][0]=x #1~room考场都不能坐，x只能坐第room+1个考场的第一个座位
  dfs(x+1,room+1) #继续安排第x+1人，试试第1~room+1考场
  p[room+1][0]=0  #回溯
n=int(input())
m=int(input())
num=110
p=[[0 for i in range(n+1)]for j in range(n+1)]
a=[[0 for i in range(n+1)]for j in range(n+1)]
for i in range(m):
  u,v=map(int,input().split())
  a[u][v]=a[v][u]=1
dfs(1,0)
print(num)