1 条题解
-
0

// 欧拉路径 O(nlogn) #include<bits/stdc++.h> using namespace std; int n,cd[26],rd[26]; vector<int> path; vector<string> wd; //单词 vector<vector<pair<int,int>>> e(26); //邻接表 int p[26]; //p[x]表示点x当前处理到第几条出边,初始值为0,相当于全局指针 void dfs(int x,int id){ //x点,x点的入边编号 for(int i=p[x]; i<e[x].size(); i=p[x]){ p[x]=i+1; dfs(e[x][i].first, e[x][i].second); } if(id!=-1) path.push_back(id); //记录入边编号 } int main(){ ios::sync_with_stdio(0); cin.tie(0); cin>>n; for(int i=0; i<n; i++){ string s; cin>>s; wd.emplace_back(s); } sort(wd.begin(),wd.end()); //单词升序 for(int i=0; i<n; i++){ int u=wd[i][0]-'a'; int v=wd[i][wd[i].size()-1]-'a'; e[u].push_back({v,i}); //i表示单词序 cd[u]++; rd[v]++; } for(int i=0; i<26; i++)if(!e[i].empty()) sort(e[i].begin(),e[i].end(), //对每个字母的出边按单词序排序 [&](pair<int,int>& a,pair<int,int>& b){return a.second<b.second;}); int cs=0,rs=0; bool ok=true; //存在欧拉路 for(int i=0; i<26; i++){ if(rd[i]!=cd[i]){ if(cd[i]-rd[i]==1) cs++; //出度多1的点数 else if(rd[i]-cd[i]==1) rs++; //入度多1的点数 else ok=false; //度差>1,一定不存在欧拉路 } } if(!(!cs&&!rs || cs==1&&rs==1)) ok=false; //非环非路一定不存在 int start=0; while(!cd[start]) ++start; //找环的起点 for(int i=0; i<26; i++) if(cd[i]-rd[i]==1){start=i; break;} //找路的起点 dfs(start,-1); //搜索欧拉路 if(path.size()!=n) ok=false; //如果不连通 if(!ok) return cout<<"***\n",0; for(int i=path.size()-1; i>=0; i--){ cout<<wd[path[i]]; if(i) cout<<'.'; } return 0; }
- 1
信息
- ID
- 12484
- 时间
- 1000ms
- 内存
- 128MiB
- 难度
- 5
- 标签
- 递交数
- 36
- 已通过
- 17
- 上传者