问题描述 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 样例输入 5 10 1 2 1 3 1 4 1 5 2 3 2 4 2 5 3 4 3 5 4 5 样例输出 5
一开始的思路是，
建图，认识的两个人，边关系标记为-1然后遍历每个点，从该点开始搜索只要两条边不认识，就将该点加入到集合中（并且要判断集合里之前加入过的点和该点是否有联系）但是这不是最优的，只拿到了40分，后来想了想还是只能暴力过。
暴力的思路是： 判断之前所有的考场是否能将当前学生放入，能就放，不能就重新开辟考场。 然后需要剪支
import java.io.BufferedInputStream; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStream; import java.io.InputStreamReader; import java.io.PrintWriter; import java.util.StringTokenizer; public class Main { static InputReader in = new InputReader(new BufferedInputStream(System.in)); static PrintWriter out = new PrintWriter(System.out); static int n, m, cnt = 0; static int[][] adj = new int[105][105]; static int[][] room = new int[105][105]; static int[] len = new int[105]; // 存放每个考场的人数 static int res = Integer.MAX_VALUE; static void dfs(int u, int total) { if (total >= res) { return ; } if (u == n+1) { res = Math.min(res, total); return ; } // 遍历所有的考场, 哪个考场可以放下当前学生, 则填进去 int i; for (i = 0; i < total; i++) { boolean flag = true; for (int j = 0; j < len[i]; j++) { int v = room[i][j]; if (adj[u][v] == -1) { flag = false; break; } } if (flag) { room[i][len[i]++] = u; dfs(u+1, total); len[i]--; // 回溯 } } // 如果均不能放, 则重新建立一个考场 if (i == total) { // 均有关，开辟新考场 room[total][len[total]++] = u; dfs(u+1, total+1); len[total]--; } } public static void main(String[] args) { n = in.nextInt(); m = in.nextInt(); for (int i = 0; i < m; i++) { int a = in.nextInt(); int b = in.nextInt(); adj[a][b] = -1; adj[b][a] = -1; } dfs(1, 0); out.println(res); out.flush(); out.close(); } static class InputReader { static BufferedReader br; static StringTokenizer st; public InputReader(InputStream stream) { br = new BufferedReader(new InputStreamReader(stream), 32768); st = null; } public String next() { while(st == null || !st.hasMoreTokens()) { try { st = new StringTokenizer(br.readLine()); } catch (IOException e) { // TODO Auto-generated catch block e.printStackTrace(); } } return st.nextToken(); } public String readLine() { String s = null; try { s = br.readLine(); } catch (IOException e) { // TODO Auto-generated catch block e.printStackTrace(); } return s; } public int nextInt() { return Integer.parseInt(next()); } public Double nextDouble() { return Double.parseDouble(next()); } public Long nextLong() { return Long.parseLong(next()); } } }