HDU 4496 Tutor 2013 ACM-ICPC吉林通化全国邀请赛E题

九野的博客，转载请注明出处： http://blog.csdn.net/acmmmm/article/details/10820117

题意：给定n个点（0 - n-1) m条边

在n个点组成的完全图中去边，问去掉一条边后的连通分量是多少

数据保证m>= (n-1) * n/2， 也就是最后去掉了所有的边

这里可以把题目看作是反向建图，从最后给定的边开始把n个独立的点相连，然后并查集

#include<stdio.h>#include<algorithm>#include<iostream>#include<set>#include<math.h>#define N 10001#define M 100050using namespace std;int father[N];int find(int x){if(x!=father[x])father[x]=find(father[x]);return father[x];}int ans[M],s[M],t[M];int main(){int n,m,i;while(~scanf("%d%d",&n,&m)){for(i=0;i<=n;i++)father[i]=i;for(i=1;i<=m;i++)scanf("%d%d",&s[i],&t[i]);ans[m]=n;for(i=m;i>1;i--){int a=find(s[i]),b=find(t[i]);if(find(a)!=find(b)){father[a]=b;ans[i-1]=ans[i]-1;}else ans[i-1]=ans[i];}for(i=1;i<=m;i++)printf("%d\n",ans[i]);}return 0;}