记录编号	481545	评测结果	AAAAWAAAAA
题目名称	726.[SDOI 2007] 单词接龙游戏	最终得分	90
用户昵称	PSI	是否通过	未通过
代码语言	C++	运行时间	0.129 s
提交时间	2018-01-03 13:54:54	内存使用	5.32 MiB

#include <cstring>
#include <algorithm>
#include <cstdio>
#include <map>
#include <queue>
#include <stack>

using namespace std;
const int MAXN = 10010;
const int MAXM = 500000;
const int MAXL = 110;
int _w;

struct Vector {
    int a[26];
    Vector() {
        memset(a, 0, sizeof a);
    }
    bool operator<( const Vector &rhs ) const {
        for( int i = 0; i < 26; ++i )
            if( a[i] < rhs[i] ) return true;
            else if( a[i] > rhs[i] ) return false;
        return false;
    }
    int &operator[]( int i ) {
        return a[i];
    }
    const int &operator[]( int i ) const {
        return a[i];
    }
};
typedef map<Vector,int>::iterator miter;
map<Vector,int> id;
int nid;
char s[MAXN][MAXL];

void input() {
    static char str[MAXL];
    while( scanf( "%s", str ) != -1 ) {
        int n = (int)strlen(str);
        Vector v;
        for( int i = 0; i < n; ++i )
            v[str[i] - 'a']++;
        if( !id.count(v) ) {
            id[v] = ++nid;
            for( int i = 0; i <= n; ++i )
                s[nid][i] = str[i];
        }
    }
}

namespace G {
    int head[MAXN], nxt[MAXM], to[MAXM], eid;
    void init() {
        eid = 0;
        memset(head, -1, sizeof head);
    }
    void adde( int u, int v ) {
        to[eid] = v, nxt[eid] = head[u], head[u] = eid++;
    }
}

void build() {
    G::init();
    for( miter it = id.begin(); it != id.end(); ++it ) {
        Vector v = it->first;
        int u = it->second;
        for( int i = 0; i < 26; ++i ) {
            ++v[i];
            id.count(v) ? G::adde(u, id[v]) : void();
            --v[i];
        }
    }
}

int f[MAXN], in[MAXN], g[MAXN];
queue<int> q;
void solve() {
    using namespace G;
    build();
    for( int i = 1; i <= nid; ++i )
        for( int e = head[i]; ~e; e = nxt[e] )
            ++in[to[e]];
    for( int i = 1; i <= nid; ++i )
        if( !in[i] )
            q.push(i), f[i] = 1, g[i] = 0;
    while( !q.empty() ) {
        int u = q.front(); q.pop();
        for( int i = head[u]; ~i; i = nxt[i] ) {
            int v = to[i];
            if( f[u] + 1 > f[v] )
                f[v] = f[u] + 1, g[v] = u;
            --in[v] ? void() : q.push(v);
        }
    }
}

stack<int> stk;
void output() {
    int u = 1;
    for( int i = 2; i <= nid; ++i )
        f[i] > f[u] ? u = i : 0;
    printf( "%d\n", f[u] );
    return;
    while(u) stk.push(u), u = g[u];
    while( !stk.empty() )
        puts( s[stk.top()] ), stk.pop();
}

int main() {
		freopen("wordgame.in","r",stdin);	
	freopen("wordgame.out","w",stdout);
    input(), solve(), output();
    return 0;
}