1 条题解
-
0

// 欧拉路径 O(nlogn) #include<bits/stdc++.h> using namespace std; int n,du[52]; int g[52][52]; vector<int> path; vector<vector<int>> e(52); //邻接表 int p[52]; //p[x]表示点x当前处理到第几条出边,初始值为0,相当于全局指针 void dfs(int x){ for(int i=p[x]; i<e[x].size(); i=p[x]){ p[x]=i+1; //指向下一条边 int y=e[x][i]; if(g[x][y]){ g[x][y]--; g[y][x]--; //删除正反边 dfs(y); } } path.push_back(x); } int main(){ ios::sync_with_stdio(0);cin.tie(0); cin>>n; for(int i=1,a,b;i<=n;i++){ string s; cin>>s; if(s[0]>='A' && s[0]<='Z') a=s[0]-'A'; else a=s[0]-'a'+26; if(s[1]>='A' && s[1]<='Z') b=s[1]-'A'; else b=s[1]-'a'+26; e[a].push_back(b); e[b].push_back(a); //无向边 g[a][b]++; g[b][a]++; du[a]++; du[b]++; } for(int i=0; i<52; i++)if(!e[i].empty()) sort(e[i].begin(),e[i].end()); //按邻接点排序 int start=53,cnt=0; for(int i=0; i<52; i++)if(du[i]&1){ //如果度为奇数 start=min(start,i); cnt++; } if(!(cnt==0||cnt==2)) //如果奇点数非0非2,则无解 return cout<<"No Solution\n",0; if(start==53)for(int i=0; i<52; i++) if(du[i]){start=i; break;} //找出环的起点 dfs(start); if(path.size()-1!=n) //如果不连通,则无解 return cout<<"No Solution\n",0; reverse(path.begin(),path.end()); for(auto i:path){ if(i>=0 && i<26) cout<<(char)(i+'A'); else cout<<(char)(i-26+'a'); } }
- 1
信息
- ID
- 12483
- 时间
- 1000ms
- 内存
- 128MiB
- 难度
- 6
- 标签
- 递交数
- 50
- 已通过
- 16
- 上传者