//.....无向图...两条边都要加入....掉了两次坑了.....还有 剪枝的时候，==也要考虑到，不能只考虑到大于的情况....会超时
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cstdlib> #include <stack> #include <vector> #include <queue> #define ll long long #define INF 0x3f3f3f3f using namespace std; const int N = 110; int graph[N][N];//存储两个同学的关系 vector<int> Room[N];//N个考场 int n, m, cnt = 0, numr = N, nump = 0; void dfs(int a, int num) { if(num >= numr){ return; } if(a == n+1){ // cout << a << " " << num <<endl; numr = num; // cout << " " << numr <<endl; return; } //在已存在的考场里找合适的位置 for(int i=0; i<num; i++){//第i+1个考场 bool flag = true; for(vector<int>::iterator it = Room[i].begin(); it != Room[i].end(); it++){ int p = *it; if(graph[a][p]){//认识，标记 flag = false; } } if(flag){//未被标记 Room[i].push_back(a); //进入这个教室 dfs(a+1, num);//安排下一个同学 Room[i].pop_back();//弹出刚加入的同学 } } //重新找一个考场 Room[num].push_back(a); dfs(a+1, num+1); Room[num].pop_back(); } int main() { cin >> n >> m; memset(graph, 0, sizeof(graph)); for(int i=0; i<m; i++){ int a, b; cin >> a >> b; graph[a][b] = 1; graph[b][a] = 1; } dfs(1, 0);//从第一个学生开始 cout << numr << endl; return 0; }
