Create a gist now

Instantly share code, notes, and snippets.

TCO 2012 Round 3A 250 ChromaticNumber
#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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment