【図論】B 057_LC_試験場を分ける(図の着色+できるだけ新しい試験場を避ける)

n人はある特殊試験を受けます.公平のために、どの2人の知っている人にも同じ試験場に分けてはいけない.いくつかの試験場を分けてこそ条件を満たすことができる.
1行目、1つの整数n(1行目、1行目、1つの整数m)を入力し、次にm行データがあることを示すm行毎のフォーマットは、2つの整数a,bであり、a番目の個人とb番目の個人の認識をスペースで区切る(1<=a,b<=n)ことで表す.
1行1つの整数を出力して、少なくともいくつかの試験場に分けられることを示します.

    
5
8
1 2
1 3
1 4
2 3
2 4
2 5
3 4
4 5
    
4

方法1:dfs
図の着色:少なくとも何色が必要かを聞いて、図を染め終わることができて、しかも隣接するノードの色は異なっています
最低の試験場が必要なので、すべての結点は歴史の中の試験場を検査して分配できるかどうかを見て、できるだけ入って、新しい試験場を分配しません...
一つの試験場に入る条件は、試験場の中の人は誰も知らないことです.

#include
using namespace std;
const int N=105;
int n, m, ans=INT_MAX/2, mk[N][N], cnt[N];  //mk[i][j]   i     j      ，cnt[i]  i       
bool knew[N][N];

void dfs(int i, int s) {    //c       ，s     
    if (s>=ans) return;
    if (i>n) {
        if (s<ans) ans=s;
        return;
    }
    for (int j=1; j<=s; j++) { //       
        int noknew=0;
        for (int k=1; k<=cnt[j]; k++) if (!knew[i][mk[j][k]]) {
            noknew++;
        }
        if (noknew==cnt[j]) {
            cnt[j]++, mk[j][cnt[j]]=i;
            dfs(i+1, s);
            cnt[j]--;
        }
    }
    cnt[++s]++, mk[s][cnt[s]]=i;
    dfs(i+1, s);
    cnt[s]--;
}

int main() {
    std::ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for (int k=0; k<m; k++) {
        int u,v; cin>>u>>v;
        knew[u][v]=knew[v][u]=true;
    }
    dfs(1, 0);
    cout << ans;
    return 0;
}