3 31 22 31 34 21 23 4 Sample Output12HintNew ~~~ Notice: if there are no road connecting one town ,tony may forget about the town.In sample 1,tony and his friends just form one group,they can start at either town 1,2,or 3.In sample 2,tony and his friends must form two group. Source2009 Multi-University Training Contest 12 - Host by FZU Recommendgaojie | We have carefully selected several similar problems for you: 3013 3015 3016 3011 3010題解：歐拉圖
用并查集維護連通性。對于同一個連通塊中的點，如果所有點的度都是偶數，那么該連通塊中存在歐拉回路。如果有K個奇數度的結點，那么需要k/2條路徑來覆蓋。
#include<iostream>#include<cstring>#include<algorithm>#include<cstdio>#include<cmath>#define N 500003using namespace std;int n,m,tot,nxt[N],point[N],v[N],cnt,sz,x[N],y[N],ans,fa[N];int dfsn[N],low[N],st[N],top,ins[N],belong[N],du[N],size[N];struct data{ int bl,x;}a[N];int cmp(data a,data b){ return a.bl<b.bl;}int find(int x){ if (fa[x]==x) return x; fa[x]=find(fa[x]); return fa[x];}int main(){ freopen("a.in","r",stdin); freopen("my.out","w",stdout); while (scanf("%d%d",&n,&m)!=EOF) { memset(du,0,sizeof(du)); tot=0; ans=0; for (int i=1;i<=n;i++) fa[i]=i; for (int i=1;i<=m;i++) { scanf("%d%d",&x[i],&y[i]); int r1=find(x[i]); int r2=find(y[i]); if (r2!=r1) fa[r2]=r1; du[x[i]]++; du[y[i]]++; } for (int i=1;i<=n;i++) fa[i]=find(i),a[i].x=i,a[i].bl=fa[i]; sort(a+1,a+n+1,cmp); int k=0; int s=0; // for (int i=1;i<=n;i++) cout<<du[i]<<" "; // cout<<endl; for (int i=1;i<=n;i++) if (a[i].bl!=a[i-1].bl||i==n) { if (i==n&&a[i].bl==a[i-1].bl) { s++; if (du[a[i].x]&1) k++; } //cout<<k<<" "<<s<<" "<<ans<<endl; if (k) ans+=k/2; else if (s>1) ans++; k=0; s=1; if (du[a[i].x]&1) k=1; }else { if (du[a[i].x]&1) k++; s++; } printf("%d/n",ans); }}
新聞熱點
疑難解答
