题意：给定n个点和m条边，问你拆掉前i条边后，整个图的连同城市的数量。
i从1到m。
思路：计算连通的城市，很容易想到并查集，但是题目里是拆边，所以我们可以反向去做。
存下拆边的信息，从后往前建边。
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct node
{
int a,b;
}Q[100005];
int set[10005];
int ans[100005];
void init(int n)
{
int i;
for(i=0;i<n;i++)
{
set[i]=i;
}
}
int find(int x)
{
int i,j,r = x;
while (set[r] != r)
r = set[r];
i = x;
while (i != r)
{
j = set[i];
set[i] = r;
i = j;
}
return r;
}
int merge(int x,int y)
{
int k,q;
k=find(x);
q=find(y);
if(k==q) return 0; //合并失败，说明他们本来就连通
set[q]=k;return 1; //合并成功，连通区域减1
}
int main()
{
int n,m,a,b;
while(~scanf("%d%d",&n,&m))
{
int top=0;
int sum=0;
for(int i=1;i<=m;i++)
scanf("%d%d",&a,&b),Q[top].a=a,Q[top++].b=b;
init(n);
if(m) ans[sum++]=n;
int tot=n;
for(int i=top-1;i>0;i--)
{
if(merge(Q[i].a,Q[i].b)) ans[sum++]=--tot;
else ans[sum++]=tot;
}
for(int i=sum-1;i>=0;i--)
{
printf("%d\n",ans[i]);
}
}
return 0;
}