jsp旅游网站开发关键技术,南京企业网站制作哪家好,购买网站做网页游戏,互联网大厂有哪些1 /*2 NYOJ 99单词拼接:3 思路#xff1a;欧拉回路或者欧拉路的搜索#xff01;4 注意#xff1a;是有向图的#xff01;不要当成无向图#xff0c;否则在在搜索之前的判断中因为判断有无导致不必要的搜索#xff0c;以致TLE!5 有向图的欧拉路#xff1a;ab… 1 /*2 NYOJ 99单词拼接:3 思路欧拉回路或者欧拉路的搜索4 注意是有向图的不要当成无向图否则在在搜索之前的判断中因为判断有无导致不必要的搜索以致TLE!5 有向图的欧拉路abs(In[i] - Out[i])1(入度[i] - 出度[i])的节点个数为两个 6 有向图的欧拉回路所有的节点都有In[i]Out[i] 7 */ 8 #includeiostream9 #includecstring10 #includecstdio11 #includealgorithm12 using namespace std;13 14 struct node{15 char s[35];16 int first, end;17 };18 19 bool cmp(node a, node b){20 return strcmp(a.s, b.s) 0;21 }22 23 node nd[1005];24 int In[30], Out[30];25 int order[1005], vis[1005]; 26 int n;27 28 int fun(){29 memset(vis, 0, sizeof(vis));30 int i; 31 int last-1; 32 int first-1; 33 //有向图欧拉路的判断 34 for(i0; i26; i) 35 { 36 if(In[i]!Out[i]) 37 { //首先入度和出度之差的绝对值为 1的节点的要么没有要么只有两个没有欧拉回路只有欧拉路 38 if(Out[i]-In[i]1 first-1) 39 firsti; 40 else if(Out[i]-In[i]-1 last-1) 41 lasti; 42 else 43 return -1; 44 } 45 } 46 if(first-1 last-1) //这种情况是 欧拉路的搜索 47 return first; 48 else if(first-1 last-1) //这种是欧拉回路的搜索 49 { 50 for(i0; i26; i) 51 if(In[i]!0) 52 return i; 53 } 54 else 55 return -1; 56 }57 58 bool dfs(int st, int cnt){ 59 if(cnt n)60 return true; 61 int ld0, rdn-1;62 while(ldrd){63 int mid(ldrd)/2;64 if(nd[mid].firstst)65 ldmid1;66 else rdmid-1; 67 }68 int mrd1;69 if(nd[m].first st) return false;70 for(int im; in; i)71 if(!vis[i]){ 72 if(nd[i].first st)73 return false;74 if(nd[i].first st){75 vis[i]1;76 order[cnt]i;77 if(dfs(nd[i].end, cnt1)) return true; 78 vis[i]0; 79 }80 } 81 return false;82 }83 84 85 int main(){86 int t;87 scanf(%d, t);88 while(t--){89 scanf(%d, n);90 memset(In, 0, sizeof(In));91 memset(Out, 0, sizeof(Out));92 for(int i0; in; i){93 scanf(%s, nd[i].s);94 nd[i].firstnd[i].s[0]-a;95 nd[i].endnd[i].s[strlen(nd[i].s)-1]-a;96 Out[nd[i].first];97 In[nd[i].end];98 } 99
100 int st fun();
101 //因为搜索的是字典序的第一个所以将字符串从小到大排一下序在搜索的时候按照升序搜索组合
102 sort(nd, ndn, cmp);
103 if(st-1 || !dfs(st, 0))
104 printf(***\n);
105 else{
106 printf(%s, nd[order[0]].s);
107 for(int i1; in; i)
108 printf(.%s, nd[order[i]].s);
109 printf(\n);
110 }
111 }
112 return 0;
113 } 转载于:https://www.cnblogs.com/hujunzheng/p/3900428.html
