POJ 2513 Colored Sticks

問題

両端にそれぞれ色が塗られている棒が複数与えられ、色が同じ棒の端同士を連結して一本の棒にすることができる。与えられた棒をすべて連結することはできるか答えよ。

やりかた

やっていることはしりとりと同じ。各色をグラフ上の頂点とみなし、棒を辺を考えれば、問題はすべての辺を一回ずつ通ることができるかという問いになる。これは準オイラーグラフ以上になっているかどうか判定すればいい。よって各頂点の次数のうち奇数になる頂点が2以下になるかどうか調べればいい。
なお、そのまえにグラフが連結であること調べておく必要がある。色はハッシュにしてintで管理する。

以下ソース。

vector<int> g[300000];
int enc[300000];
bool vis[300000];
int V;

int base = 1007;
int mod = 273113;

//文字列をハッシュに変換
int ro_hash(char *s){
  int L = strlen(s);
  int hash = 0;
  for(int i = 0; i < L; i++) hash = (hash + s[i]) * base % mod;
  if(enc[hash] != -1) return enc[hash];
  return enc[hash] = V++;
}

//連結性の判定
void rec(int idx, int prev){
  vis[idx] = true;
  for(int i = 0; i < g[idx].size(); i++)
    if(g[idx][i] != prev && !vis[g[idx][i]])
      rec(g[idx][i], idx);
  return;
}

int main(){
  char s[15], t[15];
  V = 0;
  memset(enc, -1, sizeof(enc));
  memset(vis, false, sizeof(vis));
  while(~scanf("%s %s", s, t)){
    int fr = ro_hash(s);
    int to = ro_hash(t);
    g[fr].push_back(to);
    g[to].push_back(fr);
  }
  
  rec(0, -1);
  if(count(vis, vis + V, false) != 0){
    printf("Impossible\n");
    return 0;
  }

  int odd = 0;
  for(int i = 0; i < V; i++) //次数が奇数である頂点数を数える
    odd += (g[i].size() % 2);
  printf("%s\n", odd <= 2 ? "Possible" : "Impossible");
}