第一行国际惯例——咕咕咕。
第二行——你还差的远呢。
本篇博客只针对无向图（我还没做过有向图的题
首先是两个定义（欧拉回路和欧拉路径
欧拉回路：每条边恰好只走一次，并能回到出发点的路径
欧拉路径：经过每一条边一次，但是不要求回到起始点
1.构成欧拉回路的要求：
每个顶点的度数都是偶数，则存在欧拉回路。
2.构成欧拉路径的要求：
除了起始终止两个点度数为奇数，其余顶点的度数都是偶数，则存在欧拉路径。
上面的图都要求为连通图（用并查集判断
其实题目大多会问：给你一个图，能不能用一笔画成啊？这样的。
然后，如果不连通的话，有几个不连通就需要几笔。
题目链接HRBUST1658
思路：
1.先判断是否联通
2.再判断是否奇点只有2or0个（本题可以为欧拉回路也可以为欧拉路径
3.我还加了个判断重边，不加应该也行吧，数据应该会保证的，我没试
代码
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; int f[101]; int tofind(int x) { while(f[x]!=x) x = f[x]; return x; } void liantong(int a,int b) { int r1 = tofind(a); int r2 = tofind(b); if(r1==r2) return; else f[a] = r2; } int main() { int n; scanf("%d",&n); while(n--) { int p,q; int t[101]; bool vis[101][101] = {0}; int tot = 0; memset(t,0,sizeof(t)); scanf("%d%d",&p,&q); for(int i = 1; i <= p; ++i) f[i] = i; for(int i = 0; i < q; ++i) { int a,b; scanf("%d%d",&a,&b); liantong(a,b); if(vis[a][b]==0) { t[a]++; t[b]++; } vis[a][b] = 1; vis[b][a] = 1; } int sum = 0; for(int i = 1; i <= p; ++i) if(f[i] == i) sum++; if(sum>1) { cout<<"No"<<'\n'; continue; } for(int i = 1; i <= p; ++i) { if(t[i]%2==1) tot++; } if(tot == 0||tot == 2) printf("Yes\n"); else printf("No\n"); } return 0; }
再附一个题目链接HDU1878
这个就要求必须是欧拉回路，即所有度数全部为偶数。上面的代码略作改动即可。
再补充一个模板题HihoCoder1176
欢迎指出错误qwq
