首页 > 代码库 > 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;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。