Submission #19172000

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std ;
#define sz(x) int(x.size())

const int N = 18;

// adjacency Matrix
bool ed[N][N];

bool good[1<<N];

int dp[1<<N];

int main()
{
    ios_base::sync_with_stdio(0);
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=m;++i)
    {
        int x,y;
        cin>>x>>y;
        --x,--y;
        ed[x][y] = ed[y][x] = true;
    }
    for(int i=1;i<(1<<n);++i)
    {
        vector<int> u;
        for(int j=0;j<n;++j)
            if(i&(1<<j))
                u.push_back(j);
        good[i] = true;
        for(int j=0;j<sz(u);++j)
        {
            for(int k=j+1;k<sz(u);++k)
            {
                if(!ed[u[j]][u[k]])
                    good[i] = false;
            }
        }
    }
    for(int i=0;i<(1<<n);++i)
        dp[i] = 1e9;
    dp[0] = 0;
    for(int i=1;i<(1<<n);++i)
    {
        if(good[i])
            dp[i] = 1;
        for(int j=i;j;j=(j-1)&i)
        {
            dp[i] = min(dp[i],dp[j]+dp[i^j]);
        }
    }
    cout<<dp[(1<<n)-1]<<"\n";
    return 0;
}

Submission Info

Judge Result