k染色——2020-camp-day3-C

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <cmath>
typedef long long ll;
using namespace std;
int n,m;
int maps[25][25];
bool Isok[(1<<18)+100];
int dp[(1<<18)+100];

bool check(int S){
    for(int i=1;i<=n;i++){
        if(S&(1<<(i-1))){
            for(int j=1;j<=n;j++){
                if(j==i) continue;
                if(S&(1<<(j-1))){
                    if(maps[i][j]==1) return false;
                }
            }
        }
    }
    return true;
}


void init(){
    for(int i=0;i<(1<<n);i++){
        if(check(i)) Isok[i]=true;
    }
}


int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        int u,v;scanf("%d%d",&u,&v);
        maps[u][v]=1;maps[v][u]=1;
    }
    init();
    memset(dp,0x3f,sizeof(dp));
    dp[0]=0;
    //cout<<" sss"<<endl;
    for(int S=0;S<(1<<n);S++){
        for(int S0=S;S0>0;S0=(S0-1)&S){
            if(Isok[S0]) dp[S]=min(dp[S],dp[S^S0]+1);
        }
    }
    printf("%d
",dp[(1<<n)-1]-1);
    return 0;
}