图论->欧拉迹 c++代码实现

题目类型：图论->欧拉迹
算法：看c++图算法 （Robert Sedgewick著）上的算法，大体上就是深搜（上边用栈讲解的）
时间复杂度：O(E)
题意很赤裸裸，开始要判断没有欧拉迹情况（顶点出入度），如果有欧拉回路要确定开始顶点，
因为需要考虑字典序，这个就需要对边按字符串排序，之后深搜按字符串由小到大即可保证；
从看题，看书，到过了这个题用了2.5小时...我的形式语言作业啊，还没有写...抓紧了
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
const int Max = 1024;
struct T{
    char str[32];
    int v;
    bool operator<(const T&a)const {
        if(strcmp(str, a.str) < 0)return true;
        return false;
    }
};
vector<T> lis[Max], mis[Max];
int in[32], out[32], mark[32], matrix[32][32], x[Max], xnum;
void dfs(int op, int &sum);
void search(int op);
void solve(int op);
int main()
{
    int t, n;
    scanf("%d", &t);
    while(t--){
        scanf("%d", &n);
        for(int i = 0; i < 26; i++)
            lis[i].clear();
        memset(in , 0, sizeof in);
        memset(out, 0, sizeof out);
        memset(mark, 0, sizeof mark);
        memset(matrix, 0, sizeof matrix);
        int u;
        char str[32];
        for(int i = 0; i < n; i++){
            T ans;
            scanf("%s", str);
            u = str[0] - 'a';
            ans.v = str[strlen(str) - 1] - 'a';
            strcpy(ans.str,str);
            lis[u].push_back(ans);
            in[ans.v]++, out[u]++;
            mark[u] = mark[ans.v] = 1;
            matrix[u][ans.v] = matrix[ans.v][u] = 1;
        }
        int sum = 0, tn = 0;
        for(int i = 0; i < 26; i++)if(mark[i]){tn++;}
        memset(mark, 0, sizeof mark);
        dfs(u, sum);
        if(sum != tn){
            printf("***\n");
            continue;
        }
        else {
            int v, vflag = -1, vn = 0, vm = 0, vx = 0;
            for(int i = 0; i < 26; i++){
                if(in[i] - out[i] == -1)vflag = i, vn++;
                if(in[i] - out[i] == 1)v = i, vm++;
                if(abs(in[i] - out[i]) > 1)vx = -1;
            }
            if(vx == -1 || !((vn == 0 && vm == 0) || (vn == vm == 1))){
            printf("***\n");
            continue;
            }
            for(int i = 0; i < 26; i++)
                if(lis[i].size())
                sort(lis[i].begin(), lis[i].end()), mis[i] = lis[i];
            if(vflag > -1)
                solve(vflag);
            else {
                int i = 0;
                for(i = 0; i < 26; i++)
                    if(out[i])break;
                solve(i);
            }
        }
    }
}
void solve(int op)
{
    xnum = 0;
    search(op);
    for(int i = xnum-1; i > 0; i--){
        for(int j = 0; j < (int)mis[x[i]].size(); j++)
            if(mis[x[i]][j].v == x[i-1]){
            mis[x[i]][j].v = -1;
            cout<<mis[x[i]][j].str;
            break;
            }
        printf("%c", i == 1 ? '\n' : '.');
    }
}
void search(int op)
{
    for(int i = 0; i <(int)lis[op].size(); i++) //注意要使i从小到大，即lis[op][i]中字符串由小到大；
        if(lis[op][i].v >= 0)
        {
            int tmp = lis[op][i].v;
            lis[op][i].v = -1;
            search(tmp);
        }   
    x[xnum++] = op;
}
void dfs(int op, int &sum)
{
    mark[op] = 1;
    sum++;
    for(int i = 0; i < 26; i++)
        if(mark[i] == 0 && matrix[op][i])dfs(i, sum);
}