poi2012 Tour de Byteotia

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

一眼题,不解释。。

#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);
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter