gistfile1.cpp

#include <string>
#include <vector>
#include <set>
#include <map>
#include <utility>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <iostream>
#include <queue>
#include <deque>
#include <sstream>

using namespace std;
using namespace __gnu_cxx;

#define REP(i,n) for(int i=0;i<(int)n;++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()

#define pb push_back
#define mp make_pair
#define debug(x) std::cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << std::endl;
template <class T> inline vector<T> split(string x) { vector<T> r; stringstream ss(x); T t; while(ss >> t) r.pb(t); return r; }

struct edge {
  int dest;
  int id;
  edge (int id, int dest) : id(id), dest(dest) {}
};

vector<vector<edge> > g;
map<pair<int, vector<bool> >, bool> memo;

bool dfs(int step, int next, vector<bool> used) {
  map<pair<int, vector<bool> >, bool>::iterator m = memo.find(mp(next, used));
  if(m != memo.end()) return m->second;
  bool is_win = false;
  FOR(it, g[next]) {
    if(!used[it->id]) {
      vector<bool> next_used(used);
      next_used[it->id] = true;
      if(!dfs(step+1, it->dest, next_used)) {
        is_win = true;
        break;
      }
    }
  }
  memo[mp(next, used)] = is_win;
  return is_win;
}

int main() {
  string word;
  REP(i, 26) g.push_back(vector<edge>());
  int n = 0;
  for(;;) {
    cin >> word;
    if(cin.eof()) break;
    g[word[0] - 'a'].push_back(edge(n++, word[word.size()-1] - 'a'));
  }
  vector<bool> used(n);
  dfs(0, word[word.size()-1] - 'a', used);
}