C++语言: poj 2337 并查集+欧拉通路+贪心思维+dfs #include <iostream> #include <cstring> #include <memory> #include <stack> #include <algorithm> #include <cstdio> #include <vector> using namespace std; #define mset(x) (memset(x,0,sizeof(x))) #define MAXN 26 struct node { int v; bool vis; char str[24]; node() { v=0; vis=false; } bool operator < (const node &n) const { return strcmp(str,n.str)<0; } }; int n; vector<node> brige[MAXN]; int fa[MAXN]; stack<char *> sta; bool used[MAXN];/*记录字母是否出现*/ int in[MAXN],out[MAXN];/*出度和入读*/ int findfa(int x) { if(x==fa[x])return fa[x]; else return fa[x]=findfa(fa[x]); } void merge(int x , int y) { int fx=findfa(x),fy=findfa(y); if(fx==fy) return; else fa[fx]=fy; } /*判断是否存在欧拉路*/ /*如果存在欧拉路====>(如果所有点的度数都为偶数则id=-1 否则id=i)*/ bool have_euler(int &key) { int in_num=0,out_num=0; key=-1; for(int i=0 ; i<MAXN ; ++i) { if(used[i]) { if(in[i]==out[i])continue; else if(in[i]-out[i]==1) in_num++; else if(out[i]-in[i]==1) out_num++,key=i; else return false; } } /*任意一点都可以开始*/ if(in_num==0&&out_num==0) return true; else if(in_num==1&out_num==1) return true; else return false; } /*所有点能连通*/ /*所有点都被历遍且只有一个同样的父亲 (图中每个点都至少有一条边与其他点相连)*/ bool have_onefa() { int cnt=0; for(int i=0;i<MAXN;++i) { if(used[i]&&fa[i]==i) cnt++; } return cnt==1; } void find_eulerpath(int key) { int size=brige[key].size(); for(int i=0 ; i<size ; ++i) { int v=brige[key][i].v; if(!brige[key][i].vis) { brige[key][i].vis=1; find_eulerpath(v); sta.push(brige[key][i].str); } } } void print_path() { char *str = sta.top(); sta.pop(); printf("%s",str); while(!sta.empty()) { str = sta.top(); sta.pop(); printf(".%s",str); } printf("\n"); } int main() { //freopen("C:\\Users\\bryant\\Desktop\\out.txt","w",stdout); int T; char str[24]; scanf("%d",&T); while(T--) { mset(in),mset(out),mset(used); scanf("%d",&n); for(int i=0 ; i<MAXN ;++i) { fa[i]=i; brige[i].clear(); } while(!sta.empty())sta.pop(); for(int i=0 ; i<n ;++i) { scanf("%s",str); int len = strlen(str)-1; int x=str[0]-'a',y=str[len]-'a'; node edge; edge.v = y; memcpy(edge.str,str,sizeof(edge.str)); brige[x].push_back(edge); used[x]=used[y]=true; in[y]++,out[x]++; merge(x,y); } int key=0; /*存在欧拉路且能走遍所有点*/ bool _can = have_euler(key)&&have_onefa(); if(_can) { /*贪心的思维,与每个点所接通的点都以对应字符串字典序最小排列*/ for(int i=0 ; i < MAXN ; ++i) { if(used[i]) sort(brige[i].begin(),brige[i].end()); } /*所有点的度数都为偶数,选择任意一个点都能找到欧拉路*/ if(key==-1) { /*选择字典序最小的点开始*/ for(int i=0;i<26;i++) { if(used[i]) { find_eulerpath(i); break; } } } else find_eulerpath(key); print_path(); } else puts("***"); } return 0; }