删边
题目：
n个点m条边的无向图，依次删去其中的k条边。求每一次删去一条边之后，图中连通块的个数。
1<=n<=100000,0<=k<=m<=100000。
按照题目所说的意思去想的话，很容易想到先建一个图，然后依次把这k条边删去，每次统计联通块的个数。
这个思路很明显不可行，首先怎样删边？其次，删边之后统计联通块的个数是很麻烦的，就算能求出联通块那么数据范围也肯定会炸。
然后就想，删边不好删，但是加边很好加呀。所以题目说依次删去k条边，我们不如就倒着依次加上这k条边，每次统计联通块的个数。
最后把答案倒着输出。这样解决了删边的问题，但是统计联通块似乎还是没有很好的解决，然后我就想到了并查集，我们不建图，而是把要
加的边的两个端点所在的并查集给合并，这样每合并一个并查集，就将联通块的个数-1（初始为n），然后按照上面反向加边的思路进行操作即可。
代码：
1 #include<cstdio> 2 #include<iostream> 3 #include<algorithm> 4 using namespace std; 5 const int N=100010,M=100010; 6 struct node{ 7 int u,v; 8 }a[M],b[M],c; 9 bool operator < (const node &aa,const node &bb) 10 { 11 if(aa.u!=bb.u) 12 return aa.u<bb.u; 13 return aa.v<bb.v; 14 } 15 bool operator >(const node &aa,const node &bb) 16 { 17 if(aa.u!=bb.u) 18 return aa.u>bb.u; 19 return aa.v>bb.v; 20 } 21 int fa[N],head[N],n,m,k,js,ans[M]; 22 int ff(int x) 23 { 24 if(fa[x]==x) return x; 25 return fa[x]=ff(fa[x]); 26 } 27 void uni(int x,int y) 28 { 29 int fx=ff(x),fy=ff(y); 30 fa[fx]=fy; 31 return; 32 } 33 int main() 34 { 35 scanf("%d%d%d",&n,&m,&k); 36 for(int i=1;i<=k;++i) 37 { 38 scanf("%d%d",&b[i].u,&b[i].v); 39 a[i]=b[i]; 40 } 41 js=n; 42 for(int i=1;i<=n;++i) 43 fa[i]=i; 44 sort(b+1,b+k+1); 45 for(int i=1,x,y;i<=m;++i) 46 { 47 48 scanf("%d%d",&x,&y); 49 c.u=x,c.v=y; 50 int f=lower_bound(b+1,b+k+1,c)-b; 51 if((b[f].u==c.u&&b[f].v==c.v)||(b[f].u==c.v&&b[f].v=c.u)) continue; 52 if(ff(x)!=ff(y)) 53 { 54 uni(x,y); 55 js--; 56 } 57 } 58 for(int i=k;i>=1;--i) 59 { 60 int u=a[i].u,v=a[i].v; 61 ans[i]=js; 62 if(ff(u)!=ff(v)) 63 { 64 --js; 65 uni(u,v); 66 } 67 } 68 for(int i=1;i<=k;++i) 69 printf("%d ",ans[i]); 70 return 0; 71 }
，感觉有些诈骗短信就这么发的