题意：给你一个图，可能不连通，问你需要几笔把所有边不重复的覆盖。
思路：欧拉回路的一个性质：
对于一个连通图而言，有这样的一个性质：其需要画的笔数=度数为奇数的点数除以2，那么由于给出的图并没有说明是否是连通图，我们需要用并查集来维护连通图，并且忽略单点的“子图”。
虽然早先就知道这个性质了，但是还是做了不少时间。还会码力不够。。。
AC Code：
#include<iostream> #include<cstring> #include<queue> #include<map> #include<set> #include<stack> #include<cmath> #include<cstdio> #include<iomanip> #include<sstream> #include<algorithm> using namespace std; #define read(x) scanf("%d",&x) #define Read(x,y) scanf("%d%d",&x,&y) #define sRead(x,y,z) scanf("%d%d%d",&x,&y,&z) #define gc(x) scanf(" %c",&x); #define mmt(x,y) memset(x,y,sizeof x) #define write(x) prllf("%d\n",x) #define INF 0x3f3f3f3f #define ll long long #define mod 998244353 #define pdd pair<double,double> const int N= 1e5+5; int du[N]; int pre[N]; bool vis[N]; int Find(int x) { return pre[x] == -1?x:pre[x] = Find(pre[x]);} int Size[N];//记录连通块的大小 int cnt = 0;//连通块编号 int id[N];//映射 int num[N];//存放每一个点数大于等于2的连通块奇数结点的个数 void init(){ cnt = 0; mmt(pre,-1); mmt(vis,0); mmt(num,0); } int main() { //freopen("input.txt","r",stdin); int n,m; while(scanf("%d%d",&n,&m) == 2){ init(); int u,v; fill(Size+1,Size+n+1,1); for(int i = 1;i <= m;++i){ Read(u,v); du[v]++;du[u]++; u = Find(u),v = Find(v); if(u != v){ pre[u]= v; Size[v] += Size[u]; } } for(int i = 1;i <= n;++i){ int fa = Find(i); if(Size[fa]>1){ if(vis[fa] == 0) {vis[fa] = 1;id[fa] = ++cnt;} if(du[i]&1) num[id[fa]] ++; } du[i] = 0; } int ans = 0; for(int i = 1;i <= cnt;++i){//显然若一个存在边的连通块，奇数节点的个数为0,那么这个连通块就存在欧拉回路，只需一笔。 if(num[i]) ans += num[i]/2; else ans ++; } cout<<ans<<endl; } }学到了一个更简洁的做法
int x[N],y[N],fa[N],du[N],f[N]; int Find(int x) {return fa[x] == 0?x:fa[x] = Find(fa[x]);} int main(){ int n = read(),m = read(); rep(i,1,m){ x[i] = read(),y[i] = read(); f[x[i]] = f[y[i]] = 1; du[x[i]] ++;du[y[i]] ++; } rep(i,1,n) if(du[i]%2) du[i]= 1;else du[i] = 0; for(int i = 1;i <= m;++i){ int q = Find(x[i]),p = Find(y[i]); if(q != p){ fa[q] = p; du[p] += du[q]; } } ll ans = 0; for(int i = 1;i <= n;++i) if(f[i]&&Find(i)==i){ if(du[i]<2) ans ++;else ans += du[i]/2;//偶数度数图也需要至少一笔 } if(ans == 1) puts("YES"); else{ puts("NO"); cout<<ans; } }
