Solution UVA: 193 - Graph Coloring

 

Problem	Verdict	Lang	Time	Best	Rank	Submit Time
| discuss193 - Graph Coloring	Accepted	C++11	0.040	0.000	2822	1 mins ago

Suggest:

- Only 2 state to Recurive Backtracking (u black or u white, with u from 1-> n)

* I have a close branch used to stop early, but I think we don't need this and it's still acceptable

#include<bits/stdc++.h>

#define pb push_back

using namespace std;

const int N= 1000111;

int t, n, m, u, v, maxBlack, minWhite;

vector<int> a[N];

int color[N];

vector<int> res;

void f(int u, int white, int black){

    if (minWhite < white) return;

   

    if (white + black == n){

       

        if (maxBlack < black){

            maxBlack= black;

            minWhite= white;

            res.clear();

            for(int i=1; i<=n; i++)

                if (color[i]==1) res.pb(i);

        }

        return;

    }

   

    bool ok= true;

    for(auto v:a[u])

        if (color[v]==1){

            ok= false;

            break;  

        }

    if (ok){

        color[u]= 1;

        f(u+1, white, black+1);

       

        color[u]= 0;

        f(u+1, white+1, black);

    }

    else{

        color[u]= 0;    

        f(u+1, white+1, black);

    }

}

void reset(){

    for(int i=1; i<=n; i++) color[i]= -1, a[i].clear();

    maxBlack= 0;

    minWhite= 1000111000;

}

int main(){

    ios_base::sync_with_stdio(false);

    cin.tie(nullptr);

   

    cin >> t;

    while(t--){

        cin >> n >> m;

       

        reset();

       

        while(m--){

           

            cin >> u >> v;

            a[u].pb(v);

            a[v].pb(u);

        }

        f(1, 0, 0);

        cout<<maxBlack<<"\n";

        if (not res.empty()) cout<<res[0];

        for(int i=1; i<res.size(); i++) cout<<" "<<res[i];

        cout<<"\n";

    }

}

Quay lại định kỳ