poj 2337 Catenyms

点击打开链接poj2377

思路: 并查集+排序+欧拉道路
分析:
1 题目要求的是，是否可以组成欧拉道路并且输出字典序最小的方案
2 和别的题目不一样的是这一题的输出是最小的字典序，所以这里面是一个难点，那么我们应该怎么做呢？其实我们只要对输入的n个单词进行从小到达排序即可
3 然后我们先去判断该有向图是否是单连通的
4 我们去判断是否最多只有两个点的入度不等与出度，其余所有点的出度等于入度
5 如果都满足的话，进行dfs。那么这里面就要注意了，由于要输出路径所以我们必须要这些满足的边（对应单词）压到栈里面，那么这里面就会涉及到字典序最小的问题
6 里面涉及到递归的深刻理解，所以应该要熟练递归的应用

代码:

#include<stack>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int N = 30;
int n;
int father[N] , inDegree[N] , outDegree[N];
char words[1010][N];
bool vis[1010];
stack<string>st;
vector<int>v[N];

//排序函数
int cmp(const void *s1 , const void *s2){
    return strcmp((char *)s1 , (char *)s2);
}

void init(){
    memset(vis , false , sizeof(vis));
    memset(inDegree , 0 , sizeof(inDegree));
    memset(outDegree , 0 , sizeof(outDegree));
    for(int i = 0 ; i < N ; i++){
        father[i] = i;
        v[i].clear();
    }
}

int find(int x){
    if(x != father[x])
       father[x] = find(father[x]);
    return father[x];
}

//压栈
void push(int x , int y){
    //这里应该要注意的是由于栈是先入后出所以必须先把字典序大的压入
    for(int i = n-1 ; i >= 0 ; i--){
       if(!vis[i] && words[i][0]-'a' == x){
          if(y == words[i][strlen(words[i])-1]-'a'){
             st.push(words[i]);
             vis[i] = true;
             return;
          }
       }
    }
}

//计算欧道路
void dfs(int cur){
    while(!v[cur].empty()){
         int tmp = *(v[cur].begin());
         v[cur].erase(v[cur].begin());
         dfs(tmp);
         push(cur , tmp);
    }
}

//输出
void output(){
    while(!st.empty()){
        cout<<st.top();
        st.pop();
        if(!st.empty())
           printf(".");
    }
    printf("\n");
}

void solve(){
    int root;
    for(int i = 0 ; i < N ; i++){
       if(vis[i]){
          root = find(i);
          break;
       }
    }
    for(int i = 0 ; i < N ; i++){
       if(vis[i] && root != find(i)){
          puts("***");
          return;
       }
    }
    int cnt = 0;
    for(int i = 0 ; i < N ; i++){
        if(abs(inDegree[i]-outDegree[i]) > 1){
           puts("***");
           return;
        }
        if(abs(inDegree[i]-outDegree[i]) == 1)
            cnt++;
    }
    if(cnt > 2)
        puts("***");
    else{
        int start;
        for(int i = 0 ; i < N ; i++){
            if(outDegree[i]-inDegree[i] == 1){
               start = i;
               break;
            }
        }
        if(!cnt)
           start = words[0][0]-'a';
        memset(vis , false , sizeof(vis));
        dfs(start);
        output();
    }
}

int main(){
    int Case;
    scanf("%d" , &Case);
    while(Case--){
        scanf("%d" , &n);
        init();
        for(int i = 0 ; i < n ; i++)
           scanf("%s" , words[i]);
        qsort(words , n , sizeof(words[0]) , cmp);
        for(int i = 0 ; i < n ; i++){
           int x = words[i][0]-'a';
           int y = words[i][strlen(words[i])-1]-'a';
           v[x].push_back(y);
           vis[x] = vis[y] = true;
           outDegree[x]++;
           inDegree[y]++;
           father[find(x)] = find(y);
        }
        solve();
    }
    return 0;
}