前置技能：
①顶点 $ v_1 $ 到 $ v_l $ 的拟路径：$ v_1, e_1,v_2,e_2,v_3,\cdots,v_{l-1},e_{l-1},v_l$，其中$ e_i=<v_i,v_{i+1}>$。拟路径中的边数目称作拟路径的长度。
②（欧拉）路径：拟路径中的边各不相同（允许顶点重复）；
③（欧拉）通路：路径中的顶点各不相同；
④闭路径：$ v_1 = v_l $ 的路径；
⑤（欧拉）回路：$ v_1 = v_l $ 的通路；
⑥路径和通路定理：在有n个顶点的图G中，若有顶点u到v的拟路径，则u到v必有路径，并且必定有长度不大于n-1的通路（考虑模拟路径中重复顶点的压缩）；
⑦闭路经和回路定理：在有n个顶点的图G中，若有顶点v到v的闭路径，则必定有一条从v到v的长度不大于n的回路；
⑧欧拉图：图G上有一条经过所有顶点、所有边的闭路径（边不重复，允许顶点重复），即该图中仅有一条欧拉回路。半欧拉图：图G中仅有一条欧拉通路而无欧拉回路。
⑨连通图：图中任意一对顶点都是连通的。在一个无向图G中，若从顶点i到顶点j有路径相连（当然从j到i也一定有路径），则称i和j是连通的。如果G是有向图，那么连接i和j的路径中所有的边都必须同向。
a、在有向图中, 若对于每一对顶点v1和v2, 都存在一条从v1到v2和从v2到v1的路径，则称此连通图是强连通图。
b、将有向图的所有的有向边替换为无向边，所得到的图称为原图的基图。如果一个有向图的基图是连通图，则有向图是弱连通图。
充要条件判定：注意：都不存在孤立点。
①欧拉回路（欧拉图）：
a、无向图：G连通，所有顶点的度都是偶数；
b、有向图：G弱连通，每个顶点的出度与入度相等。
②欧拉通路（欧拉路径）：考虑起始顶点的度的特殊情况
a、无向图：G连通，恰有两个顶点的度是奇数；
b、有向图：G弱连通，恰有两个顶点的出度与入度不相等，其中一个出度比入度多1，另一个入度比出度多1。
题解报告：hdu 1878 欧拉回路
Problem Description
Input
Output
Sample Input
Sample Output
1 #include2 using namespace std; 3 typedef long long LL; 4 const int maxn=1005; 5 int T,n,m,deg[maxn],fa[maxn],a,b,f1,f2; 6 void init(){ 7 for(int i=1;i<=n;++i)fa[i]=i; 8 } 9 int findt(int x){10 int per=x,tmp;11 while(fa[per]!=per)per=fa[per];12 while(x!=per){tmp=fa[x];fa[x]=per;x=tmp;}13 return x;14 }15 void unite(int x,int y){16 x=findt(x),y=findt(y);17 if(x!=y)fa[x]=y;18 }19 int main(){20 while(cin>>n&&n){21 cin>>m;22 memset(deg,0,sizeof(deg));init();f1=f2=0;23 while(m--){24 cin>>a>>b;25 deg[a]++,deg[b]++;26 unite(a,b);27 }28 for(int i=1;i<=n;++i)29 f1+=(i==fa[i]?1:0),f2+=(deg[i]&1?0:1);30 if(f1==1&&f2==n)puts("1");///欧拉回路：每个顶点的度为偶数31 else puts("0");32 33 }34 return 0;35 }
题解报告：NYOJ 42 一笔画问题
Problem Description
zyc从小就比较喜欢玩一些小游戏，其中就包括画一笔画，他想请你帮他写一个程序，判断一个图是否能够用一笔画下来。规定，所有的边都只能画一次，不能重复画。
Input
第一行只有一个正整数N(N<=10)表示测试数据的组数。
每组测试数据的第一行有两个正整数P,Q(P<=1000,Q<=2000)，分别表示这个画中有多少个顶点和多少条连线。（点的编号从1到P）随后的Q行，每行有两个正整数A,B(0<A,B<P)，表示编号为A和B的两点之间有连线。Output
如果存在符合条件的连线，则输出"Yes",如果不存在符合条件的连线，输出"No"。
Sample Input
2
4 31 21 31 44 51 22 31 31 43 4Sample Output
No
Yes解题思路：一笔画问题即判断无向图是否具有欧拉通路或者欧拉回路，先用并查集判断无向图是否连通，再判断是否有0个或2个奇数度的顶点即可。
AC代码：
1 #include2 using namespace std; 3 typedef long long LL; 4 const int maxn=1005; 5 int T,n,m,deg[maxn],fa[maxn],a,b,f1,f2; 6 void init(){ 7 for(int i=1;i<=n;++i)fa[i]=i; 8 } 9 int findt(int x){10 int per=x,tmp;11 while(fa[per]!=per)per=fa[per];12 while(x!=per){tmp=fa[x];fa[x]=per;x=tmp;}13 return x;14 }15 void unite(int x,int y){16 x=findt(x),y=findt(y);17 if(x!=y)fa[x]=y;18 }19 int main(){20 while(cin>>n>>m){21 memset(deg,0,sizeof(deg));init();f1=f2=0;///f1判断是否是连通图，f2统计偶数度的顶点个数22 while(m--){23 cin>>a>>b;24 deg[a]++,deg[b]++;25 unite(a,b);26 }27 for(int i=1;i<=n;++i)28 f1+=(i==fa[i]?1:0),f2+=(deg[i]&1?0:1);29 if(f1==1&&(f2==n||n-f2==2))puts("Yes");///如果每个节点的度都是偶数，或者恰有两个奇数度的顶点，就能一笔画出30 else puts("No");31 32 }33 return 0;34 }