UVa 193 - Graph Coloring

193.cpp

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

#define F first
#define S second
#define PB push_back
#define endl '\n'

typedef long long ll;
typedef vector<ll> vll;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<int> vi;

const int INF = ~(1 << 31);

int n, mx;
int T[107], R[107];
map<ii, bool> E;

int cont() {
    return accumulate( T, T + 107, 0 );
}

bool can_add(int c) {
    for(int i=0; i<107; i++) {
        if( T[i] && E[{ min( c, i ), max( c, i ) }] )
            return false;
    }
    return true;
}

void solve(int c) {
    if(c > n) {
        // Case base return
        int s = cont();
        if(s > mx) {
            mx = s;
            for(int i=0; i<107; i++)
                R[i] = T[i];
        }
        return;
    }

    if(can_add( c )) {
        T[c] = true;
        solve( c + 1 ); // Solution with vertex c
    }

    T[c] = false;
    solve( c + 1 ); //Solution without vertex c

}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t, m, u, v;
    cin >> t;

    while(t--) {

        cin >> n >> m;

        mx = -INF;
        E.clear();
        memset( T, 0, sizeof T );
        memset( R, 0, sizeof R );

        for(int i=0; i<m; i++) {
            cin >> u >> v;
            if(v < u) swap( u, v );
            E[{ u, v }] = true;
        }

        if(!m) {
            cout << n << endl;
            for(int i=1; i<=n; i++) {
                if(i > 1) cout << ' ';
                cout << i;
            } cout << endl;
            continue;
        }

        solve( 1 );

        vi A;
        for(int i=0; i<107; i++)
            if(R[i]) A.PB( i );

        cout << mx << endl;
        for(int i=0; i<mx; i++) {
            if(i > 0) cout <<  ' ';
            cout << A[i];
        }
        cout << endl;
    }

    return 0;
}