Catenyms

题意：给定一些单词，如果一个单词的尾字母与另一个的首字母相同则可以连接。问是否可以每个单词用一次，将所有单词连接，可以则输出字典序最小的序列。
题解：并查集+欧拉通路+贪心思维+dfs ，这一题我也是参考了别人的代码。
ps:vector的使用 ,内部堆栈的使用
  1 #include<iostream>
  2 #include<cstring>
  3 #include<algorithm>
  4 #include<cstdio>
  5 #include<vector>
  6 #include<stack>
  7 using namespace std;
  8 struct Node{
  9     int v;
 10     char ss[30];//储存每个单词 
 11      bool vis;//标记该边是否被访问 
 12        Node(){ //初始化 
 13         v=0;  
 14        vis=false; 
 15     }  
 16      bool operator<(Node a)const{//比较字符串，把字典序在前的放在前面 
 17          if(strcmp(ss,a.ss)<0)return true;
 18          else
 19            return false;
 20      }
 21 };
 22 vector<Node>map[27];
 23 int pa[30];
 24 void init(){//初始化 
 25     for(int i=1;i<=26;i++){
 26        pa[i]=-1;
 27        map[i].clear(); }
 28 }
 29 int Find(int x){//查找 
 30     int s;
 31     for(s=x;pa[s]>=0;s=pa[s]);
 32     while(s!=x){
 33         int temp=pa[x];
 34         pa[x]=s;
 35         x=temp;
 36     }
 37     return s;
 38 }
 39 void Union(int R1,int R2){//合并 
 40     int r1=Find(R1);
 41     int r2=Find(R2);
 42     int temp=pa[r1]+pa[r2];
 43     if(pa[r1]>pa[r2]){
 44         pa[r1]=r2;
 45         pa[r2]=temp;
 46     }
 47     else{
 48         pa[r2]=r1;
 49         pa[r1]=temp;
 50     }
 51 }
 52 stack<char *> sta;//储存结果集  
 53 int in[30],num;//入度 
 54 int out[30];//出度 
 55 int  used[30];//标记出现过的字母 
 56 bool judge1(){//判断是否存在欧拉路径或者欧拉回路 
 57     num==-1;int r1=0;int r2=0;
 58     int in_num=0,out_num=0;  
 59     num=-1;  
 60     for(int i=1 ; i<=26 ; ++i){  
 61         if(used[i]){  
 62             if(in[i]==out[i])continue;  
 63             else if(in[i]-out[i]==1) in_num++;  
 64             else if(out[i]-in[i]==1) out_num++,num=i;  
 65             else return false;  
 66         }  
 67     }  
 68     /*任意一点都可以开始*/  
 69     if(in_num==0&&out_num==0)  
 70     return true;  
 71     else if(in_num==1&out_num==1)  
 72     return true;  
 73     else return false;  
 74 }
 75 bool judge2(){//判断是否连通 
 76     int first =-1;
 77     for(int i=1;i<=26;i++){
 78         if(used[i]){
 79             if(first==-1)first=Find(i);
 80             else if(first!=Find(i))return false;
 81         }
 82     }
 83     return true;
 84 }
 85 void DFS(int key){//DFS寻找最小的路径  
 86      int size=map[key].size();  
 87     for(int i=0 ;i<size ; ++i){  
 88         int v=map[key][i].v;  
 89         if(!map[key][i].vis){  
 90             map[key][i].vis=1; //标记已经被访问 
 91             DFS(v); //继续收索 
 92             sta.push(map[key][i].ss);//退出时把结果放入结果集 
 93         }  
 94     }  
 95 }   
 96 int main(){
 97     int cas,n;char ss[50];
 98     scanf("%d",&cas);
 99     while(cas--){
100         memset(in,0,sizeof(in)),memset(out,0,sizeof(out)),memset(used,0,sizeof(used));
101         scanf("%d",&n);init();
102         while(!sta.empty())sta.pop();  
103         for(int i=1;i<=n;i++){
104             scanf("%s",ss);
105             int len=strlen(ss);
106             int u=ss[0]-'a'+1;int v=ss[len-1]-'a'+1;
107             out[u]++;in[v]++;used[u]=true;used[v]=true;
108             Node temp;
109             temp.v=v;strcpy(temp.ss,ss);
110             map[u].push_back(temp);
111             if(Find(u)!=Find(v))
112             Union(u,v);
113         }
114        bool  can=judge2();
115        bool  can1=judge1();        
116         if(can&&can1){
117             for(int i=1;i<=26;i++){
118                 if(used[i])
119                     sort(map[i].begin(),map[i].end());//排序，是的结果集最小 
120                 }
121                if(num==-1){  
122                   for(int i=1;i<=26;i++){  
123                     if(used[i]){//从最小的开始  
124                         DFS(i);  
125                         break;  
126                     }  
127                 }  
128             }  
129             else DFS(num); 
130             char *str = sta.top();  
131               sta.pop();  
132              printf("%s",str);  
133        while(!sta.empty()) {  
134          str = sta.top();  
135          sta.pop();  
136          printf(".%s",str);  
137       }  
138      printf("
");  
139      }
140     else puts("***");      
141   }
142 }
143
View Code