ural 1671 Anansi's Cobweb-并查集

Anansi's Cobweb

Description

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.

Input

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

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

Sample Input

input	output
4 4 1 2 2 3 1 3 3 4 3 2 4 3	1 2 3
3 1 1 2 1 1	3

Sample Output

Hint

题目大意：

n个点m个边

接下来m行  第i条边是从u到v

一个数q表示要依次删去共q条边

编号分别为什么

问 每次删掉这个边之后 这个图有几个连通分支？

解题思路

删边并不好考虑，考虑加边，如果这个边的两个顶点分别属于两个连通分支，那么他们两个相加就导致图中的连通分枝数就少1

那么我们倒着考虑，以例一为例

首先我们把不需要删除的边做一次并查集，这样相当于所有要删的边全删去后的图的连通分支数已经得到了

再加入3号边，就相当于原图删去 2号 4号边 之后有几个连通分支

再加入4号边，相当于原图删去 2号边之后有几个连通分支

2号边就不需要加入了，因为加入2号边相当于没删边有几个连通分支，题目没问。

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <bits/stdc++.h>
using namespace std;

const int maxn = 100005;

struct edge{
    int u,v;
}e[maxn];///边编号是1~m

bool ife[maxn];///这个边是不是要被删除
int de[maxn];///删边的顺序
int fa[maxn];
int result[maxn];

void init(){
    for(int i=0;i<maxn;++i)
        fa[i] = i;
}

int  findp(int x){
    int xp = x;
    while(fa[xp] != xp){
        xp = fa[xp];
    }
    int now = x,newx;
    while(fa[now] != xp){
        newx = fa[now];
        fa[now] = xp;
        now = newx;
    }
    return xp;
}

int main()
{
    init();
    int n,m,q;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;++i){
        scanf("%d%d",&e[i].u,&e[i].v);
    }
    scanf("%d",&q);
    for(int i=1;i<=q;++i){
        scanf("%d",&de[i]);
        ife[de[i]] = 1;
    }
    int ans = n;
    for(int i = 1;i<=m;++i){
        if(ife[i]) continue;///如果这条边会被删掉，就不加进去
        int uf = findp(e[i].u);
        int vf = findp(e[i].v);
        if(uf!=vf){
            fa[uf]=fa[vf];
            ans--;
       }
    }
    int j = 1;
    result[j++] = ans;
    for(int i=q;i>1;--i){///从要删的最后一条边开始加入,第一个边不用加
        int uf = findp(e[de[i]].u);
        int vf = findp(e[de[i]].v);
        if(uf!=vf){///如果两个点的父亲不一样，那么将他们连起来之后，图的连通分支数就会减一
            fa[uf]=fa[vf];
            ans--;
        }
        result[j++] = ans;
    }

    for(int i = j-1;i>0;--i){
        printf("%d",result[i]);
        if(i!=1) putchar(' ');
    }
    return 0;
}