首页 > 代码库 > URAL 1671 Anansi's Cobweb (并查集)

URAL 1671 Anansi's Cobweb (并查集)

题意:给一个无向图。每次查询破坏一条边,每次输出查询后连通图的个数。

思路:并查集。逆向思维,删边变成加边。

 

#include<cstdio>#include<cstring>#include<algorithm>#include<vector>#include<iostream>#define inf -100000000#define LL long long#define maxn 100005using namespace std;struct Edge{    int x,y;};int parent[maxn];int findset(int p){    return (parent[p]==p)?p:(parent[p]=findset(parent[p]));}Edge edge[maxn];int query[maxn];bool build[maxn];int ans[maxn];int main(){    int n,m;    while(scanf("%d%d",&n,&m)!=EOF)    {        memset(build,0,sizeof(build));        for(int i=1; i<=m; ++i)            scanf("%d%d",&edge[i].x,&edge[i].y);        int q;        scanf("%d",&q);        for(int i=1; i<=q; ++i)        {            scanf("%d",&query[i]);            build[query[i]]=true;        }        for(int i=1; i<=n; ++i)            parent[i]=i;        int cnt=0;        for(int i=1; i<=m; ++i)            if(!build[i])            {                int fa=findset(edge[i].x),fb=findset(edge[i].y);                if(fa!=fb)                    parent[fa]=fb;            }        for(int i=1; i<=n; ++i)            if(findset(i)==i) cnt++;        for(int i=q; i>=1; --i)        {            ans[i]=cnt;            int fa=findset(edge[query[i]].x),fb=findset(edge[query[i]].y);            if(fa!=fb)            {                parent[fa]=fb;                cnt--;            }        }        for(int i=1; i<=q; ++i)            if(i==1) printf("%d",ans[i]);            else printf(" %d",ans[i]);        printf("\n");    }    return 0;}
View Code