关于为什么不选桥
因为选桥之后会变成两个联通分支，这时由于可能产生的新联通分支不是孤立顶点，他俩都不联通了，那么也就绝对不可能“一笔画”走下来了
关于为什么可以选除桥之外的任意一条边走
本质原因是因为环与环嵌套后这俩环是没有内外之分的，所以说你任意选一条边本质是选择在哪个环上走，而你走任何一个环最后都是回到出发点，所以就随便走
其实欧拉图就是环套环或者环套环套环或者环套环套环套环或者...的图
#include<bits/stdc++.h>
using namespace std;
int mtx[][];
int deg[];
bool vis[];
bool dfs(int u,int v){
vis[u]=;
if(u==v)
return ;
for(int i=;i<;i++){
if(mtx[u][i]&&!vis[i]){
if(dfs(i,v))
return ;
}
}
return ;
}
bool not_bridge(int u,int v){ //判桥用dfs判的
memset(vis,,sizeof(vis));
mtx[u][v]=mtx[v][u]=;
int x=;
for(int i=;i<;i++){
if(mtx[u][i])
x++;
}
if(!x)
return ;
for(int i=;i<;i++){
if(mtx[u][i]){
if(dfs(i,v)){
mtx[u][v]=mtx[v][u]=;
return ;
}
}
}
mtx[u][v]=mtx[v][u]=;
return ;
}
int fa[];
int getfa(int x){ //并查集判一下是不是只有一个连通分量
while(x!=fa[x])
x=fa[x];
return x;
}
void joint(int u,int v){
fa[getfa(v)]=getfa(u);
}
int main(){
int n;
cin>>n;
char t[];
int minch='z'+-'A';
for(int i=;i<=;i++)
fa[i]=i;
for(int i=;i<=n;i++){
cin>>t;
int u=t[]-'A';
minch=min(minch,u);
int v=t[]-'A';
minch=min(minch,v);
if(getfa(u)!=getfa(v))
joint(u,v);
mtx[u][v]=;
deg[u]++;
mtx[v][u]=;
deg[v]++;
}
int prefa=-;
for(int i=;i<=;i++){
if(deg[i]){
if(prefa==-)
prefa=getfa(i);
else{
if(prefa!=getfa(i)){
puts("No Solution");
return ;
}
}
}
}
int odd=;
for(int i=;i<;i++){
if(deg[i]%){
odd++;
}
if(odd>){
puts("No Solution");
return ;
}
}
if(odd==){
minch='z'+-'A';
for(int i=;i<;i++){
if(deg[i]%){
minch=min(minch,i);
}
}
}
queue<int> Q;
Q.push(minch);
while(!Q.empty()){
int temp=Q.front();
Q.pop();
cout<<(char)(temp+'A');
for(int i=;i<;i++){
if(mtx[temp][i]&¬_bridge(temp,i)){
mtx[temp][i]=mtx[i][temp]=;
Q.push(i);
break;
}
}
}
return ;
}
//后来我学了hierholzer，强烈建议大家去学这个算法啊，实用多了