poj2337:http://poj.org/problem?id=2337
题意：给定一些单词，如果一个单词的尾字母与另一个的首字母相同则可以连接。问是否可以每个单词用一次，将所有单词连接，可以则输出字典序最小的序列。
题解：并查集+欧拉通路+贪心思维+dfs ，这一题我也是参考了别人的代码。
ps:vector的使用 ,内部堆栈的使用
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<vector>
#include<stack>
using namespace std;
struct Node{
int v;
char ss[];//储存每个单词
bool vis;//标记该边是否被访问
Node(){ //初始化
v=;
vis=false;
}
bool operator<(Node a)const{//比较字符串，把字典序在前的放在前面
if(strcmp(ss,a.ss)<)return true;
else
return false;
}
};
vector<Node>map[];
int pa[];
void init(){//初始化
for(int i=;i<=;i++){
pa[i]=-;
map[i].clear(); }
}
int Find(int x){//查找
int s;
for(s=x;pa[s]>=;s=pa[s]);
while(s!=x){
int temp=pa[x];
pa[x]=s;
x=temp;
}
return s;
}
void Union(int R1,int R2){//合并
int r1=Find(R1);
int r2=Find(R2);
int temp=pa[r1]+pa[r2];
if(pa[r1]>pa[r2]){
pa[r1]=r2;
pa[r2]=temp;
}
else{
pa[r2]=r1;
pa[r1]=temp;
}
}
stack<char *> sta;//储存结果集
int in[],num;//入度
int out[];//出度
int used[];//标记出现过的字母
bool judge1(){//判断是否存在欧拉路径或者欧拉回路
num==-;int r1=;int r2=;
int in_num=,out_num=;
num=-;
for(int i= ; i<= ; ++i){
if(used[i]){
if(in[i]==out[i])continue;
else if(in[i]-out[i]==) in_num++;
else if(out[i]-in[i]==) out_num++,num=i;
else return false;
}
}
/*任意一点都可以开始*/
if(in_num==&&out_num==)
return true;
else if(in_num==&out_num==)
return true;
else return false;
}
bool judge2(){//判断是否连通
int first =-;
for(int i=;i<=;i++){
if(used[i]){
if(first==-)first=Find(i);
else if(first!=Find(i))return false;
}
}
return true;
}
void DFS(int key){//DFS寻找最小的路径
int size=map[key].size();
for(int i= ;i<size ; ++i){
int v=map[key][i].v;
if(!map[key][i].vis){
map[key][i].vis=; //标记已经被访问
DFS(v); //继续收索
sta.push(map[key][i].ss);//退出时把结果放入结果集
}
}
}
int main(){
int cas,n;char ss[];
scanf("%d",&cas);
while(cas--){
memset(in,,sizeof(in)),memset(out,,sizeof(out)),memset(used,,sizeof(used));
scanf("%d",&n);init();
while(!sta.empty())sta.pop();
for(int i=;i<=n;i++){
scanf("%s",ss);
int len=strlen(ss);
int u=ss[]-'a'+;int v=ss[len-]-'a'+;
out[u]++;in[v]++;used[u]=true;used[v]=true;
Node temp;
temp.v=v;strcpy(temp.ss,ss);
map[u].push_back(temp);
if(Find(u)!=Find(v))
Union(u,v);
}
bool can=judge2();
bool can1=judge1();
if(can&&can1){
for(int i=;i<=;i++){
if(used[i])
sort(map[i].begin(),map[i].end());//排序，是的结果集最小
}
if(num==-){
for(int i=;i<=;i++){
if(used[i]){//从最小的开始
DFS(i);
break;
}
}
}
else DFS(num);
char *str = sta.top();
sta.pop();
printf("%s",str);
while(!sta.empty()) {
str = sta.top();
sta.pop();
printf(".%s",str);
}
printf("\n");
}
else puts("***");
}
}