3453.【NOIP2013中秋节模拟】连通块(connect)
Time Limits: 1000 ms Memory Limits: 262144 KB (File IO): input:connect.in output:connect.out
Description
你应该知道无向图的连通块的数量，你应该知道如何求连通块的数量。当你兴奋与你的成就时，破坏王Alice拆掉了图中的边。当她发现，每删去一条边，你都会记下边的编号，同时告诉她当前连通块的个数。 然而，对边编号简直就是个悲剧，因为Alice为了刁难你，拆掉编号从l到r的边，当然你需要做的事情就是求连通块的个数。如果你答对了，Alice会把拆掉的边装好，迚行下一次破坏。如果你无法完成这个任务，Alice会彻底毁了你的图。 进行完足够多次之后，Alice觉得无聊，就玩去了，而你却需要继续做第三题。
第一行两个整数n,m，表示点数和边数。 之后m行每行两个整数x,y，表示x与y之间有无向边。（按读入顺序给边编号，编号从1开始） 一行一个整数k，表示Alice的破坏次数。 之后k行，每行两个整数l,r。
Output
k行，每行一个整数。
6 5 1 2 5 4 2 3 3 1 3 6 6 1 3 2 5 1 5 5 5 2 4 3 3
Sample Output
4 5 6 3 4 2
Data Constraint
对于30%的数据，n<=100,k<=10 对于60%的数据，k<=1000 对于100%的数据，n<=500,m<=10000,k<=20000,1<=l<=r<=m
题解
连通块问题，典型的并查集，要加预处理
用l[i][j]记录前i条边构成的集合 用r[i][j]记录后i条边构成的集合
询问x到y被破坏时，只需要将l[x-1]和r[y+1]合并，求连通块即可
代码
#include<cstdio>
#include<cstring>
#define N 510
#define M 10010
long l[M][N],r[M][N],c[N];
long x[M],y[M],n;
bool b[N];
long cha(
long x,
long father[])
{
if(father[x]==x)
return x;
else return father[x]=cha(father[x],father);
}
void bin(
long x,
long y,
long father[])
{
long fx,fy;
fx=cha(x,father);
fy=cha(y,father);
if(fx!=fy)father[fx]=fy;
}
long suan(
long xx,
long yy)
{
long i,ans;
memcpy(c,l[xx-
1],
sizeof(l[xx-
1]));
for(i=
1;i<=n;i++)
if(r[yy+
1][i]!=i)
bin(c[i],r[yy+
1][i],c);
memset(b,
false,
sizeof(b));
ans=
0;
for(i=
1;i<=n;i++)
if(!b[cha(i,c)]){
b[cha(i,c)]=
true;
ans++;
}
return ans;
}
int main()
{
long m,i,k,xx,yy;
freopen(
"connect.in",
"r",stdin);
freopen(
"connect.out",
"w",stdout);
scanf(
"%ld%ld",&n,&m);
for(i=
1;i<=m;i++)
scanf(
"%ld%ld",&x[i],&y[i]);
for(i=
1;i<=n;i++)
l[
0][i]=r[m+
1][i]=i;
for(i=
1;i<=m;i++){
memcpy(l[i],l[i-
1],
sizeof(l[i-
1]));
bin(x[i],y[i],l[i]);
}
for(i=m;i>=
1;i--){
memcpy(r[i],r[i+
1],
sizeof(r[i+
1]));
bin(x[i],y[i],r[i]);
}
scanf(
"%ld",&k);
for(i=
1;i<=k;i++){
scanf(
"%ld%ld",&xx,&yy);
printf(
"%ld\n",suan(xx,yy));
}
return 0;
}
