欧拉路

欧拉回路 : 每条边只经过一次，而且回到起点

欧拉路径 : 每条边只经过一次，不要求回到起点

欧拉回路判断：

无向图 ：连通（不考虑度为零的点），每个顶点度数都为偶数。

有向图：基图连通（把边当成无向边，同样不考虑度为0的点），每个顶点出度等于入度。

混合图 （有有向边和无向边）:首先是基图连通(不考虑度为零的点)，然后需要借助网络流判定。
首先给原图中的每条无向边随便指定一个方向（成为初始方向），将原图改为有向图 G’ ,然后的任务就是改变 G’ 中某些边的方向（当然是无向边转化来的，原混合图中的有向边不能动）使其满足每个点的入度等于出度。
设D[ i ] 为G’ 中（点 i 的出度 -点 i 的入度） ，可以发现，在改变G’ 中的边的方向的过程中，任何点的D 值得奇偶性都不会发生改变（设将边 改为 <j,i> ,则i 入度加1出度减1，i 入度减1或出度加1，两者之差减 2 或 加2，奇偶性不变）而最终要求的是每个点的出度等于入度，即每个点的D值都为零，是偶数，故可得：若初始定向得到的G’中任意一个点的D值为奇数，那么原图中一定不存在欧拉环。
若初始D值都是偶数，则将G’改装成网络：设立源点S和汇点T,对于每个D[ i ] > 0点 i ，连边 <S,i>,容量为D[ i ] / 2;对于每个D[ j ] < 0 的点 j ，连边 <j,T>,容量为 –D[ j ]/2; G‘ 中的每条边在网络中仍保留，容量为1（表示该边最多只能边方向一次）。求这个网络的最大流，若S引出的所有边均满流，若原混合图是欧拉图，将网络中所有流量为1 的中间边（就是不与S或T关联的边）在G’ 中改变方向，形成的新图G’’ 一定是有向欧拉图；若S引出的边没有满流，则原混合图不是欧拉图。

欧拉路径判断：

无向图 ：连通（不考虑度为0 的点），每个顶点度数都是偶数或者仅有两个顶点的度数为偶数。

有向图 ：基图连通（把边当成无向边，同样不考虑度0的度），每个顶点出度等于入度或者有且仅有一个点的出度比入度多1，有且仅有一个点的出度比入度小1，其余出度等于入度。

混合图 ：如果存在欧拉回路，一点存在欧拉路径。否则如果有且仅有两个点的（出度 – 入度）是奇数，那么给这两个点加边，判断是否存在欧拉回路。

题目:
https://www.luogu.com.cn/problem/P1341
题目描述
给定n个各不相同的无序字母对（区分大小写，无序即字母对中的两个字母可以位置颠倒）。请构造一个有n+1个字母的字符串使得每个字母对都在这个字符串中出现。

输入格式
第一行输入一个正整数n。

以下n行每行两个字母，表示这两个字母需要相邻。

输出格式
输出满足要求的字符串。

如果没有满足要求的字符串，请输出“No Solution”。

如果有多种方案，请输出前面的字母的ASCII编码尽可能小的（字典序最小）的方案
输入输出样例
输入
4
aZ
tZ
Xt
aX
输出
XaZtX

看的题解…
把每个字母当作一个节点（…）自己搞字符串很懵逼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
const int MAX=3000;
int n,head,b[150][150],deg[150],f[150];
char a[2],ans[MAX]; 
int find(int x){
	return f[x]==x?x:f[x]=find(f[x]);
}
void dfs(int x){//找欧拉回路/路径 
	fi(i,64,125){
		if(b[x][i]){
			b[x][i]=b[i][x]=0;
			dfs(i);
		}
	}
	ans[n--]=x;
}
int main(){
	freopen("in","r",stdin);
	fi(i,64,125)f[i]=i;
	sf(n);
	fi(i,0,n){
		scanf("%s",a); 
		b[a[0]][a[1]] = b[a[1]][a[0]] = 1 ;
		deg[a[0]]++;
		deg[a[1]]++;
		int x=find(a[0]),y=find(a[1]);
		f[x]=y;
	}
	int cnt=0;
	fi(i,64,125){
		if(f[i]==i && deg[i])cnt++;
	}
	if(cnt!=1) { //非连通图 
		pfc("No Solution");return 0; 
	}
	cnt=0;
	head=0;
	fi(i,64,125){
		if(deg[i]&1){
			cnt++;
			if(head==0) head=i;
		}
	}
	if(cnt && cnt!=2) {//有奇度数点，且不是两个，不存在欧拉路 
		pfc("No Solution");return 0;
	}
	if(head==0)
		fi(i,64,125){
			if(deg[i]) {
				head=i;break; //字典序最小，起点 
			}
		}
	dfs(head);
	printf("%s",ans);
	return 0;
}