TCO 2012 Round 3A 250 ChromaticNumber

ChromaticNumber.cpp

#include <string>
#include <iostream>
#include <sstream>
#include <vector>
#include <cmath>
#include <queue>

using namespace std;

#define REP(i,n) for((i)=0;(i)<(int)(n);(i)++)

int n;

class ChromaticNumber {
public:
int minColors(vector <string> graph) {
  n = graph.size();
  int i,k;
  int visit[52] = {0};

  int res = 0;

  REP(k,n){
    if (visit[k]) continue;

    // start from k
    queue<int> q;
    q.push(k);
    visit[k] = 1;
    
    bool cyclic = true;
    int num = 0;

    while(!q.empty()){
      int a = q.front();
      q.pop();

      num++;

      string s = graph[a];
      int count = 0;
      REP(i,s.size()){
        if (i==a) continue;
        if (s[i]=='N') {
          count++;
          if (!visit[i]) {
            q.push(i);
            visit[i] = 1;
          }
        }
      }
      if (count != 2) cyclic = false;
    }

    if (num == 1) res += 1;
    else if (num == 3 && cyclic) {
      res += 1;
    } else {
      res += num/2 + num%2;
    }
  }
  return res;
}