P3065 [USACO12DEC]First! G

Trie+拓扑排序。
P3065 USACO12DECFirst! G
假定当前字符串是最小的，然后在Trie上跑一遍，字典序小的字母向字典序大的字母连边。
然后拓扑排序成环就与猜测冲突（即不能为最小的）
注：字典序先按字母排序，然后按长度。
所以遇到前缀相同的，长的必定不行。

#include <iostream>
#include <cstring>
#include <cstdio>
#include <stack>

using namespace std;

typedef long long ll;
const ll MAXN = 1e6+10;

struct nod {
    ll nt[26], vis;
} t[MAXN];

struct edge {
    ll nt, to;
} E[MAXN];

ll N, cnt = 0, rk[26], head[26], ecnt = -1, tot, ans[MAXN];
string ss[MAXN];

void add(ll, ll);
bool check(string);
void inser(string);
bool tope();

int main() {
    cin >> N;
    for (ll i = 1; i <= N; i++) {
        cin >> ss[i];
        inser(ss[i]);
    }
    for (ll i = 1; i <= N; i++) {
        memset(rk, 0, sizeof(rk));
        memset(head, -1, sizeof(head));
        ecnt = -1;
        if (check(ss[i])) {
            if (tope()) {
                ans[++tot] = i;
            }
        }
    }
    cout << tot << endl;
    for (ll i = 1; i <= tot; i++) {
        cout << ss[ans[i]] << endl;
    }
    return 0;
}

bool tope() {
    stack<ll> st;
    for (ll i = 0; i < 26; i++) {
        if (!rk[i]) {
            st.push(i);
        }
    }
    while (!st.empty()) {
        ll nt = st.top(); st.pop();
        for (ll i = head[nt]; ~i; i = E[i].nt) {
            ll v = E[i].to;
            rk[v]--;
            if (!rk[v]) st.push(v);
        }
    }
    for (ll i = 0; i < 26; i++) {
        if (rk[i]) {
            return false;
        }
    }
    return true;
}

bool check(string tem) {
    ll len = tem.length(), now = 0;
    for (ll i = 0; i < len; i++) {
        ll gg = tem.at(i) - 'a';
        if (t[now].vis) return false;
        for (ll i = 0; i < 26; i++) {
            if (t[now].nt[i] && gg != i) {
                add(gg, i);
            }
        }
        now = t[now].nt[gg];
    }
    return true;
}

void add(ll x, ll y) {
    ecnt++;
    E[ecnt].nt = head[x];
    E[ecnt].to = y;
    rk[y]++;
    head[x] = ecnt;
}

void inser(string tem) {
    ll now = 0, len = tem.length();
    for (ll i = 0; i < len; i++) {
        ll gg = tem.at(i) - 'a';
        if (!t[now].nt[gg]) {
            t[now].nt[gg] = ++cnt;
        }
        now = t[now].nt[gg];
    }
    t[now].vis = 1;
}