P1197 [JSOI2008]星球大战
题意
略(中文)
思路
一道思维并查集题,正着摧毁貌似不是很行,那就倒着修建,预处理按修建的顺序排序然后用并查集记录连通块个数就行了.
代码
#include<bits/stdc++.h>
using namespace std
;
const int maxn
=4e5+10;
struct node
{
int x
,y
,id
;
bool operator < (const node
& b
) const {
return id
<b
.id
;
}
}a
[maxn
];
int b
[maxn
],fa
[maxn
],ans
[maxn
];
int n
,m
,num
;
int find(int x
){
if(x
!=fa
[x
])
return fa
[x
]=find(fa
[x
]);
else return x
;
}
void merge(int x
,int y
){
x
=find(x
);
y
=find(y
);
if(x
!=y
) {
fa
[x
]=y
;
num
--;
}
}
int main(){
scanf("%d%d",&n
,&m
);
num
=n
;
for(int i
=0;i
<n
;i
++) fa
[i
]=i
;
for(int i
=1;i
<=m
;i
++){
scanf("%d%d",&a
[i
].x
,&a
[i
].y
);
a
[i
].id
=0;
}
int t
;scanf("%d",&t
);
for(int i
=1;i
<=t
;i
++){
int x
;scanf("%d",&x
);
b
[x
]=t
-i
+1;
}
for(int i
=1;i
<=m
;i
++) a
[i
].id
=max(b
[a
[i
].x
],b
[a
[i
].y
]);
sort(a
+1,a
+m
+1);
for(int i
=0,j
=1;i
<=t
;i
++){
for(;a
[j
].id
==i
;j
++) merge(a
[j
].x
,a
[j
].y
);
ans
[i
]=num
-(t
-i
);
}
for(int i
=t
;i
>=0;i
--) printf("%d\n",ans
[i
]);
return 0;
}
