poi2012 Tour de Byteotia

stupid_lulu posted @ 2013年3月26日 02:08 in poi , 4298 阅读

一眼题，不解释。。

poi2012 Tour de Byteotia
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34	`#include<cstdio>` `int` `n,m,k,ans=0;` `int` `fa[1000001];` `struct` `re{` `int` `u,v;` `} a[2000001];` `re b[2000001];` `int` `getfa(int` `x){return` `fa[x]==x? x:fa[x]=getfa(fa[x]);}` `int` `main(){` `//freopen("tou1a.in","r",stdin);` `scanf("%d%d%d",&n,&m,&k);` `for` `(int` `i=1;i<=n;i++) fa[i]=i;` `for` `(int` `i=1;i<=m;i++){` `scanf("%d%d",&a[i].u,&a[i].v);` `if` `(a[i].u<=k\|\|a[i].v<=k)` `continue;` `int` `fx=getfa(a[i].u);` `int` `fy=getfa(a[i].v);` `if` `(fx!=fy){` `fa[fx]=fy;` `}` `}` `for` `(int` `i=1;i<=m;i++){` `if` `(a[i].u>k&&a[i].v>k)` `continue;` `int` `fx=getfa(a[i].u);` `int` `fy=getfa(a[i].v);` `if` `(fx==fy){` `ans++;` `b[ans].u=a[i].u;` `b[ans].v=a[i].v;` `}` `else` `fa[fx]=fy;` `}` `printf("%d\n",ans);` `for` `(int` `i=1;i<=ans;i++)` `printf("%d %d\n",b[i].u,b[i].v);` `}`