Play on Words

题目链接

• 思路：
  欧拉回路解
• 关键：
  欧拉回路的要求是每个边只访问一次且遍历所有边。这个题目中的要求是每个单词只使用一边，且访问所有单词。所以我们显然可以将每个单词拆成边来构图。比如对于a*****b单词，我们可以a -> i -> b（a和b要换成数字且不与单次序号冲突，i是这个单词的序号）
• 反思：
  判断欧拉回路必须判断两个条件：连通和对应的要求，缺一不可

C++AC，G++CE

const int MAXN = 110000;

struct Direct_Euler
{
    int out[MAXN], father[MAXN];
    vector<int> vt[MAXN];
    stack<int> sk;
    typedef pair<int, int> pii;
    set<pii> st;

    void init()
    {
        st.clear();
        while (!sk.empty())
            sk.pop();
        REP(i, MAXN)
        {
            father[i] = i;
            vt[i].clear();
        }
        CLR(out, 0);
    }
    int find(int n)
    {
        return father[n] == n ? n : father[n] = find(father[n]);
    }
    bool isOne(int n)
    {
        int t = find(0);
        REP(i, n)
        {
            if (find(i) != t)
                return false;
        }
        return true;
    }
    void merge(int a, int b)
    {
        vt[a].push_back(b);
        out[a]++;
        out[b]--;
        int fa = find(a), fb = find(b);
        father[fb] = fa;
    }
    //是返回true,而且如果是欧拉回路circle = 0,如果是欧拉路circle > 0
    //不是返回false
    bool isEulerRoad(int n, int& circle, int& ind)
    {
        if (!isOne(n))
            return false;
        int end = 0, same = 0;
        circle = 0;
        REP(i, MAXN)
        {
            if (out[i] == 1)
            {
                if (++circle > 1) return false;
                ind = i;
            }
            else if (out[i] == -1)
                end++;
            else if (out[i] == 0)
                same++;
        }
        return (circle + end + same == MAXN);
    }
    void dfs(int n)
    {
        REP(i, vt[n].size())
        {
            int next = vt[n][i];
            if (!st.count(MP(n, next)))
            {
                st.insert(MP(n, next));
                dfs(next);
                sk.push(n);
            }
        }
    }
} graph;

int main()
{
//    freopen("in.txt", "r", stdin);
    int n, ncase;
    RI(ncase);
    while (ncase--)
    {
        graph.init();
        RI(n);
        REP(i, n)
        {
            RS(ipt);
            graph.merge(ipt[0] - ‘a‘ + 1000, i);
            graph.merge(i, ipt[strlen(ipt) - 1] - ‘a‘ + 1000);
        }
        int ind, tot;
        if (!graph.isEulerRoad(n, tot, ind))
            puts("The door cannot be opened.");
        else
            puts("Ordering is possible.");
    }
    return 0;
}

Play on Words,布布扣,bubuko.com

Play on Words

原文：http://blog.csdn.net/wty__/article/details/21523795