[演算法心得] UVA 193. Graph Coloring

#include<bits/stdc++.h>

#define ll long long

#define INF 0x3f3f3f3f

#define MOD 1000000007

#define io ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);

using namespace std;

const int MXN = 200005;

int ans = 0;

int n = 0, m = 0, k = 0;

vector<int> pathAns, color;

vector<vector<int> > path;

void dfs(int idx, int c){

  if(idx > n){

if(ans < c){

   ans = c;

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

      pathAns[i] = color[i];

   }

}

return;

  }

  for(int i = idx; i <= n; ++i){

if(n - idx + c + 1 <= ans) return; // 剪枝，如果當前畫最多黑色仍然不足ans就退出。

if(color[i] == 0){

   color[i] = i;

   for(int j : path[i]) if(color[j] == 0) color[j] = i;

   int now = i;

   while(color[now] && now <= n) now++;

   dfs(now, c + 1);

   for(int j = 1; j <= n; ++j) if(color[j] == i) color[j] = 0;

}

  }

}

void sol(){

  ans = 0;

  cin >> n >> m;

  path.clear();

  pathAns.clear();

  color.clear();

  path.resize(n + 1);

  pathAns.resize(n + 1);

  color.resize(n + 1);

  for(int i = 0; i < m; ++i){

int s, t;

cin >> s >> t;

path[s].emplace_back(t);

path[t].emplace_back(s);

  }

  dfs(1, 0);

  cout << ans << '\n';

  int flag = 0;

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

if(pathAns[i] == i){

   if(flag){

      cout << ' ';

   }

   cout << i;

   flag = 1;

}

  }

  cout << '\n';

}

int main(){

  io

  int t = 1;

  cin >> t;

  while(t--){

sol();

  }

}
複製代碼

冰楓論壇