Timus Online Judge(Ural)1671 Anansi's Cobweb题解

Timus

题目简述：4/3/4/4/并查集

传送门：1671. Anansi's Cobweb

题面

Usatiy-Polosatiy XIII decided to destroy Anansi's home — his cobweb. The cobweb consists of N nodes, some of which are connected by threads. Let us say that two nodes belong to the same piece if it is possible to get from one node to the other by threads. Usatiy-Polosatiy has already decided which threads and in what order he would tear and now wants to know the number of pieces in cobweb after each of his actions.

输入

The first line contains integers N and M — the number of nodes and threads in the cobweb, respectively(2 ≤ N ≤ 100000; 1 ≤ M ≤ 100000). Each of the next M lines contains two different integers — the 1-based indices of nodes connected by current thread. The threads are numbered from 1 to M in the order of description. Next line contains an integer Q which denotes the quantity of threads Usatiy-Polosatiy wants to tear (1 ≤ Q ≤ M). The last line contains numbers of these threads — different integers separated by spaces.

输出

Output Q integers — the number of pieces in Anansi's cobweb after each of Usatiy-Polosatiy's action. Separate numbers with single spaces.

样例

input1:
4 4
1 2
2 3
1 3
3 4
3
2 4 3
output1:
1 2 3
input2:
3 1
1 2
1
1
output2:
3

分析

题意：给定一个n（$1\leqslant n\leqslant 10^5$）点m（$1\leqslant m\leqslant 10^5$）边的图，给定q（1\leqslant q\leqslant q）次删边操作，求删后连通块的数量

离线，然后倒序并查集，这题比较套路

代码

#include<stdio.h>
const int maxn=100005;
int i,j,k,m,n,q,now;
int f[maxn],u[maxn],v[maxn],ban[maxn],ck[maxn],ans[maxn];
int find(int x){
    return f[x]==x? x:f[x]=find(f[x]);
}
int main(){
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++)
        f[i]=i;
    for(i=1;i<=m;i++)
        scanf("%d%d",&u[i],&v[i]);
    scanf("%d",&q);
    for(i=1;i<=q;i++){
        scanf("%d",&ban[i]);
        ck[ban[i]]=1;
    }
    now=n;
    for(i=1;i<=m;i++)
        if(ck[i]==0)
            if(find(u[i])!=find(v[i]))
                now--,f[find(u[i])]=find(v[i]);
    for(i=q;i>=1;i--){
        ans[i]=now;
        if(find(u[ban[i]])!=find(v[ban[i]]))
            now--,f[find(u[ban[i]])]=find(v[ban[i]]);
    }
    for(i=1;i<=q;i++)
        printf("%d%c",ans[i],i==q? '\n':' ');
    return 0;
}