建立联系
【试题描述】
新学期开始了，不料同学们在假期集体更换了电话，所以同学们只能重新建立联系。
班内一共有n位同学，他们一共建立了m次联系，老师想知道在同学们每次建立完一个联系后，一共有多少对同学可以互相联系。
【输入要求】
第一行有两个数n和m，表示有n位同学和m次操作。
以后m行，每行两个数a和b，分别表示a号同学与b号同学之间建立了联系。
【输出要求】
输出共有m行，每行一个整数，表示第m次操作后共有多少对同学可以互相联系。
【输入实例】
5 6 1 2 2 3 4 5 1 3 2 4 4 5
【输出实例】
1 3 4 4 10 10
【其他说明】
1<=n,m<=100000
【试题分析】
为啥叫所谓的“优化AC”呢？很简单，因为只有按照优化的方法写代码才能AC，否则结果错误，并查集“敌人”那道题就是要这样的方法解决，但是不优化之前就是时间超限。维护每个并查集的大小。我们具体来看看代码。
【代码】
#include<iostream>
using namespace std;
long long x,y,f[100001],n,m,size[100001],ans;
int find(int x)
{
if (f[x]==x) return f[x];
return f[x]=find(f[x]);
}
void merge(int v,int u)
{
int t1,t2;
t1=find(v);
t2=find(u);
if(t1!=t2) {f[t2]=t1;size[t1]+=size[t2];} //合并并查集之后并查集的大小要随之增加
return ;
}
inline long long read()
{
long long x,f=1;
char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if(ch==‘-‘) f=-1;
for(x=ch-‘0‘;isdigit(ch=getchar());x=x*10+ch-‘0‘);
return x*f;
}
inline void write(long long x)
{
if(x==0){putchar(‘0‘);return;}if(x<0)putchar(‘-‘),x=-x;
int len=0,buf[15];while(x)buf[len++]=x%10,x/=10;
for(int i=len-1;i>=0;i--)putchar(buf[i]+‘0‘);return;
}
int main()
{
n=read(),m=read();
for(int i=1;i<=n;i++) f[i]=i,size[i]=1;
for(int i=1;i<=m;i++)
{
x=read(),y=read();
if(find(x)!=find(y)) {ans+=size[find(x)]*size[find(y)];merge(x,y);}//需合并两个并查集，为以后查询做准备
write(ans);
printf("\n");//不要忘了write中没有回车！！
}
}
原文：http://www.cnblogs.com/wxjor/p/5758581.html