http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1070
http://poj.org/problem?id=1386

一个单词就是一条边。
建立有向图后套模板。
(注意n为1的情况)

/*UVa: 0.045s*/
/*POJ: 360ms,5548KB*/

const int mx = 27;

int n, G[mx][mx], in[mx], out[mx];
vector<p2> ans;

void init()
{
    mem(G, 0);
    mem(in, 0);
    mem(out, 0);
}

bool ok(int &start)
{
    start = -1;
    int i, num1 = 0, num2 = 0, reserve;
    Forr(i, 1, mx)
    {
        if (out[i]) reserve = i;
        if (in[i] != out[i])
        {
            if (in[i] == out[i] + 1) ++num1;
            else if (out[i] == in[i] + 1) ++num2, start = i;
            else return false;
        }
    }
    if (start == -1) start = reserve;
    return num1 <= 1 && num2 <= 1;
}

void dfs(int u)
{
    int v;
    Forr(v, 1, mx) if (G[u][v])
    {
        --G[u][v];
        dfs(v);
        ans.PB(MP(u, v));
    }
}

bool solve()
{
    int start;
    if (!ok(start)) return false;
    ans.clear();
    dfs(start);
    return ans.size() == n;
}

char s[1005];

int main()
{
    int t, i, u, v;
    SI(t);
    while (t--)
    {
        init();
        SI(n);
        For(i, n)
        {
            SS(s);
            u = s[0] & 31, v = s[strlen(s) - 1] & 31;
            ++G[u][v], ++out[u], ++in[v];
        }
        puts(solve() ? "Ordering is possible." : "The door cannot be opened.");
    }
    return 0;
}

Comments

comments powered by Disqus