Submission #19167587

---

Source Code Expand

/**
 * Dont raise your voice, improve your argument.
 * --Desmond Tutu
 */

#include <bits/stdc++.h>
using namespace std;

const bool ready = []() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(12);
    return true;
}
();

using ld=long double;
const ld PI = acos(-1);
using ll= long long;
#define int ll
#define all(v) (v).begin(), (v).end()
#define fori(n) for(int i=0; i<int(n); i++)

#define cini(i) int i; cin>>i;
#define cins(s) string s; cin>>s;
#define cind(d) ld d; cin>>d;
#define cinai(a,n) vi a(n); fori(n) { cin>>a[i]; }
#define cinas(s,n) vs s(n); fori(n) { cin>>s[i]; }
#define cinad(a,n) vd a(n); fori(n) { cin>>a[i]; }

using pii= pair<int, int>;
using pdd= pair<ld, ld>;
using vd= vector<ld>;
using vb= vector<bool>;
using vi= vector<int>;
using vvi= vector<vi>;
using vs= vector<string>;

#define endl "\n"

/* We can add a vertex to a group if that vertex has edge to all members.
 *
 * We can merge two groups if all members of the group have eges to all
 * members of other group.
 */
const int INF=1e9;
void solve() {
    cini(n);
    cini(m);
    vector<vb> adj(n, vb(n));
    for(int i=0; i<m; i++) {
        cini(a);
        a--;
        cini(b);
        b--;
        adj[a][b]=true;
        adj[b][a]=true;
    }

    int ans=INF;
    function<void(vvi,int)> go=[&](vvi groups, const int v) {
        /* we can add the current vertex to each group possible, or to a new group */
        /*
                cerr<<"sz="<<groups.size()<<" groups="<<endl;
                for(auto vec : groups) {
                    for(int j : vec)
                        cerr<<j+1<<" ";
                    cerr<<endl;
                }
                */

        if(v==n) {
            ans=min(ans, (int)groups.size());
            return;
        }

        if((int)groups.size()>=ans)
            return;

        for(size_t i=0; i<groups.size(); i++) {
            bool ok=true;
            for(int g : groups[i]) {
                if(!adj[v][g]) {
                    ok=false;
                    break;
                }
            }
            if(ok) {
                groups[i].push_back(v);
                //cerr<<"adding v="<<v+1<<" to group="<<i<<endl;
                go(groups, v+1);
                groups[i].pop_back();
            }
        }
        vi ngroup;
        ngroup.push_back(v);
        groups.push_back(ngroup);
        go(groups, v+1);
    };

    vvi g;
    go(g, 0);
    cout<<ans<<endl;
}

signed main() {
    solve();
}

// FIRST THINK, THEN CODE
// DO NOT JUMP BETWEEN PROBLEMS

Submission Info

Judge Result