Catenyms

题目链接

• 前言：
  是这个题的复杂版，增加了输出路径的一项
• 重点：
  输出字典序最小的解，可以先对输入进行排序可以保证搜索的时候先进入小的点

const int MAXN = 1100;

string ipt[MAXN];

int cmp(string a, string b)
{
    return a < b;
}

//集合中可以有很多元素(没用到的也行)
//下标从零开始
//但是在函数isEulerRoad的第一个参数必须是前n个有用的点
//方便自己加一些点,而且不影响判断连通性
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;
    }
    // n:判断前n个点是否是一个集合(并查集使用)
    //是返回true,而且如果是欧拉回路circle = 0,如果是欧拉路circle > 0
    //不是返回false
    bool isEulerRoad(int n, int& tot, int& ind)
    {
        if (!isOne(n))
            return false;
        int end = 0, same = 0;
        REP(i, MAXN)
        {
            if (out[i] == 1)
                ++tot, ind = i;
            else if (out[i] == -1)
                end++;
            else if (out[i] == 0)
                same++;
        }
        return (tot + end + same == MAXN && tot <= 1);
    }
    //搜索路径,结果保留在sk中
    void solve(int n)
    {
        REP(i, vt[n].size())
        {
            int next = vt[n][i];
            if (!st.count(MP(n, next)))
            {
                st.insert(MP(n, next));
                solve(next);
            }
        }
        sk.push(n);
    }
    //输出路径,自己写格式
    void display()
    {
        int cnt = 0;
        vector<string> vt;
        while (!sk.empty())
        {
            int t = sk.top();
            if (t < 1000)
            {
                if (cnt != 0)
                    putchar(‘.‘);
                cout << ipt[t];
                cnt++;
            }
            sk.pop();
        }
        cout << endl;
    }
} graph;

int main()
{
//    freopen("in.txt", "r", stdin);
    int n, ncase;
    RI(ncase);
    while (ncase--)
    {
        graph.init();
        RI(n);
        REP(i, n) cin >> ipt[i];
        sort(ipt, ipt + n, cmp);
        REP(i, n)
        {
            graph.merge(ipt[i][0] - ‘a‘ + 1000, i);
            graph.merge(i, ipt[i][ipt[i].size() - 1] - ‘a‘ + 1000);
        }
        int ind = ipt[0][0] - ‘a‘ + 1000, tot = 0;
        if (graph.isEulerRoad(n, tot, ind))
        {
            graph.solve(ind);
            graph.display();
        }
        else
            puts("***");
    }
    return 0;
}

Catenyms,布布扣,bubuko.com

Catenyms

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