http://acm.hdu.edu.cn/showproblem.php?pid=3018
题意 ——许多蚂蚁 遍历一个图 每一条边只能走一次 问至少要把这些蚂蚁分为几群
说白了就是 至少几笔可以画出一个特定的 图 出来
*********************************************
欧拉回路：图G，若存在一条路，经过G中每条边有且仅有一次，称这条路为欧拉路，如果存在一条回路经过G每条边有且仅有一次，
称这条回路为欧拉回路。具有欧拉回路的图成为欧拉图。
判断欧拉路是否存在的方法
有向图：图连通，有一个顶点出度大入度1，有一个顶点入度大出度1，其余都是出度=入度。
无向图：图连通，只有两个顶点是奇数度，其余都是偶数度的。
判断欧拉回路是否存在的方法
有向图：图连通，所有的顶点出度=入度。
无向图：图连通，所有顶点都是偶数度。
*******************************************
先找出有几个 连通分支 再看连通分支中有几个 点的度数为奇数 要是奇度数为0 则加count++ 否则count+=奇度数、2;
我没有用并查集 而是dfs一遍 找出有几个连通分支并记录下每个点 所属的连通分支序号
有个要注意的地方是 他只是遍历边 要是有的点是孤立的是 不用管的 （我一开始没注意到这里 孤立的点也加上了结果 wa了好久都硬是找不到错误的地方 = = ）
我的代码:
#include<iostream> #include<string.h> #include<vector> using namespace std; vector <int> G[100002]; int c,vis[100002],du[100002],ans[100002],p[100002]; // 1到c p[i]： 第i个连通分支的 奇度数 void dfs(int n) { vis[n]=1; int len; ans[n]=c; len=G[n].size(); //i 点的连通分量的编号为ans[i] for(int i=0;i<len;i++) if(vis[G[n][i]]==0) dfs(G[n][i]); } int main() { int i,j,n,m,s,e,temp=0; while(scanf("%d%d",&n,&m)!=EOF) { for(i=0;i<=temp;i++) G[i].clear(); temp=n; c=0; memset(vis,0,sizeof(vis)); memset(du,0,sizeof(du)); memset(p,0,sizeof(p)); while(m--) { scanf("%d%d",&s,&e);du[s]++; du[e]++; G[s].push_back(e); G[e].push_back(s); // 图 } for(i=1;i<=n;i++) { if(vis[i]==0) { c++; dfs(i); } } for(i=1;i<=n;i++) if(du[i]%2==1) p[ans[i]]++; int final=0; for(i=1;i<=n;i++) { if(du[i]==0) continue; //孤立的点 忽略 if(p[ans[i]]!=-1) //该店所处的连通分支 已经加过 { if(p[ans[i]]==0) final++; else
final+=p[ans[i]]/2;
p[ans[i]]=-1; //标记 } } printf("%d\n",final); } return 0; }
黄霖的：（他用了并查集）
#include<stdio.h> #include<string.h> #include<stdlib.h> int f[100003]; int visit[1000003]; int num[100003]; void ini(int n) { int i; for(i=1;i<=n;i++) { f[i]=i; visit[i]=0; num[i]=0; } } int find(int x) { int r,i=x; while(x!=f[x]) x=f[x]; while(i!=x) { r=f[i]; f[i]=x; i=r; } return x; } void Union(int x,int y) { visit[x]++; visit[y]++; x=find(x); y=find(y); if(x==y) return ; else { f[x]=y; } } int main() { int n,m,i,k,sum,x,y; while(scanf("%d%d",&n,&m)>0) { ini(n); for(i=1;i<=m;i++) { scanf("%d%d",&x,&y); Union(x,y); } for(i=1;i<=n;i++) find(i); for(i=1;i<=n;i++) { if(visit[i]%2==1) { k=f[i]; num[k]++; } } sum=0; for(i=1;i<=n;i++) { if(visit[i]>0 && f[i]==i) { if(num[i]==0) sum++; else if(num[i]>0) sum=sum+num[i]/2; } } printf("%d\n",sum); } return 0; }
网上另外一个人的 （他的并查集 我没看懂，谁看懂了的 指点一下）
#include <iostream> #include <stdio.h> using namespace std; const int maxv = 100000 + 2; int odds[maxv]; /* 顶点 */ int du[maxv]; /* 每个顶点的度数 */ int p[maxv]; /* 并查集数组 */ bool used[maxv]; int scc[maxv]; /* scc个数 */ void init(int n) { for(int i = 0; i <= n; ++i) { odds[i] = 0; p[i] = -1; du[i] = 0; used[i] = 0; } } int utf_find(int x) { if(0 <= p[x]) { p[x] = utf_find(p[x]); return p[x]; } return x; } void utf_union(int a, int b) { int r1 = utf_find(a); int r2 = utf_find(b); if(r1 == r2) return; int n1 = p[r1]; int n2 = p[r2]; if(n1 < n2) { p[r2] = r1; p[r1] += n2; } else { p[r1] = r2; p[r2] += n1; } } int main() { int n = 0; int m = 0; int a = 0; int b = 0; int i = 0; int cnt = 0; while(scanf("%d%d", &n, &m) != EOF) { init(n); cnt = 0; for(i = 1; i <= m; ++i) { scanf("%d%d", &a, &b); du[a]++; du[b]++; utf_union(a, b); } for(i = 1; i <= n; ++i) { int f = utf_find(i); if(!used[f]) { used[f] = 1; scc[cnt++] = f; } if(1 == du[i]%2) odds[f]++; } int ret = 0; for(i = 0; i < cnt; ++i) { if(0 == du[scc[i]]) continue; if(0 == odds[scc[i]]) ++ret; else ret += odds[scc[i]]/2; } printf("%d\n", ret); } return 0; }