- // 并查集判联通, dfs 求解欧拉回路
- #include<iostream>
- using namespace std;
- const int N=150;
- int mp[N][N];// 邻接矩阵存图
- int d[N];// 点的度数
- char res[N*N];// 大于 C(52,1)*C(51,1)/2, 边数
- int n;// 边数
- void dfs(int now)
- {
- for(int i='A';i<='z';i++)// 没什么好说的
- {
- if(mp[now][i])
- {
- mp[now][i]=mp[i][now]=0;
- dfs(i);
- }
- }
- res[n--]=now;// 走到底再存, 得反过来, 如果顺着来的话, 数目有点麻烦(其实也是看别人反着来)
- }
- int fa[N];
- int finds(int x)
- {
- while(fa[x]!=x)
- {
- x=fa[x];
- }
- return x;
- }
- int main(void)
- {
- cin>>n;
- for(int i='A';i<='z';i++)
- {
- fa[i]=i;
- }// 并查集初始化
- for(int i=1;i<=n;i++)
- {
- string s;
- cin>>s;
- mp[s[0]][s[1]]=mp[s[1]][s[0]]=1;
- d[s[0]]++;// 度数加一
- d[s[1]]++;
- int f1=finds(s[0]);
- int f2=finds(s[1]);
- fa[f1]=f2;//union
- }
- int cnt=0;// 连通分量数
- for(int i='A';i<='z';i++)
- {
- if(d[i]&&fa[i]==i)
- {
- cnt++;
- }
- }
- if(cnt>1)
- {
- cout<<"No Solution"<<endl;
- return 0;
- }
- cnt=0;// 奇点数
- int head=0;// 欧拉回 (通) 路起点
- for(int i='A';i<='z';i++)
- {
- if(d[i]&1)
- {
- cnt++;
- if(head==0)
- {
- head=i;
- }
- }
- }
- if(cnt&&cnt!=2)// 奇点只能没有或者有两个
- {
- cout<<"No Solution"<<endl;
- return 0;
- }
- if(!head)// 如果没有奇点就找个最小的偶度点出发, 注意如果有奇点必须从奇点出发(错了贼久)
- {
- for(int i='A';i<='z';i++)
- {
- if(d[i])
- {
- head=i;
- break;
- }
- }
- }
- int tmp=n;
- dfs(head);
- for(int i=0;i<=tmp;i++)
- {
- cout<<res[i] ;
- }
- return 0;
- }
P1341 无序字母对(欧拉回路 + 并查集)
来源: http://www.bubuko.com/infodetail-3393517.html