Skip to content

Instantly share code, notes, and snippets.

@mechairoi
Created August 13, 2010 11:02
Show Gist options
  • Save mechairoi/522704 to your computer and use it in GitHub Desktop.
Save mechairoi/522704 to your computer and use it in GitHub Desktop.
#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);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment