P1341 欧拉回路

• 为什么会这样。。。。

我从下午起床，写到晚上睡觉的一题。

我就搞不懂了。。。cin>>s;

和getchar()到底哪里不同了。。。。

我很生气

这个测试点，怎么就过不去了？？？？

用 cin>>s就完全没有问题。。。

我枯了。。。？？？？

• 题意

虽然之前学过离散数学，但是还是没有想到这题其实 求字典序最小的欧拉回路（成环）或欧拉路径（未成环）。

参考博客：欧拉回路/路径【总结】

讲的很透彻的洛谷题解

• 划重点

欧拉路径：在一个图中，由i点出发，将每个边遍历一次最终到达j点的一条路径。 
欧拉回路： i=j时的欧拉路径。  （兜兜转转又回到了起点）

无向图：

                欧拉回路：每个点的度数都是偶数

                欧拉路径：（从奇数到奇数）如果有且仅有两个点的度数为奇数，就会存在一条从这两个中的一个到达另一个的欧拉

                                     路径。

有向图：

                欧拉回路：（有进必有出）所有点的入度等于出度，就存在一条欧拉回路。 

                欧拉路径：：最多有一点入度等于出度+1，最多有一点入度等于出度-1，就会有一条从出度大于入度（没有则等于）                                         的点出发，到达出度小于入度（没有则等于）的点的一条欧拉路径。

• 思路

首先，判断这个无向图是否连通。并查集判断，也就是大家都是一个父亲喽。

接着，判断是不是存在欧拉回路或路径。

如果存在，就要利用dfs 得到路径：

             首先，出发点我们在证明中已经确定，只需要保留路径时由后往前保存，再利用深搜回溯的过程，我们可以保证不会走    死胡同（其实是走了死胡同，但保存路径时会把这段路留到最后，就相当于没有走死）。 

• 代码

//P1341
#include<iostream>
#include<algorithm>
#include<set>
#include<cstring>
#include<queue>
#include<stack>
#include<vector>
#include<map>
#include<stdio.h>
using namespace std;
#define ll long long
map<char,int> mp;
map<char,int>::iterator it;
int num[200][200];//graph
string s;
int pre[200];
int ex[200];int n,head;
void Init()
{for(int i=64;i<126;i++)pre[i]=i;
}int find(int x)
{if(pre[x]==x) return x;return pre[x]=find(pre[x]);
}int idx=0;
char ans[2000];
int vis[60];void dfs(int x)
{for(int i=64;i<126;i++){if(num[x][i] ){num[x][i]=num[i][x]=0;dfs(i);}}ans[n--]=x;}int main()
{scanf("%d",&n);int nn=n;getchar();Init();for(int i=1;i<=n;i++){cin>>s;//        s[0]=getchar();
//        s[1]=getchar();
//        getchar();num[s[0]][s[1]]=num[s[1]][s[0]]=1;ex[s[0]]++;ex[s[1]]++;int x=find(s[0]);int y=find(s[1]);pre[x]=y;}int cnt=0;for(int i=64;i<126;i++)if(pre[i]==i && ex[i]) cnt++;//  cout<<"cnt:"<<cnt<<endl;if(cnt!=1){cout<<"No Solution"<<endl;return 0;}cnt=0;//奇数度数的点head=0;for(int i=64;i<126;i++){if(ex[i] & 1){cnt++;if(head==0) head=i;//一定会从奇数度进入}}if(cnt && cnt!=2){cout<<"No Solution"<<endl;return 0;}if(head==0)//是欧拉回路{for(int i=64;i<126;i++){if(ex[i]){head=i;break;}}}dfs(head);cout<<ans<<endl;return 0;}