首页 > 代码库 > nyoj_1022:合纵连横(并查集删点)
nyoj_1022:合纵连横(并查集删点)
http://acm.nyist.net/JudgeOnline/problem.php?pid=1022
只附代码好了
#include<bits/stdc++.h> using namespace std; const int N=200005; int a[N],b[N],vis[N]; int n,m,add,kase; void init() { for(int i=0;i<n;i++) a[i]=i,b[i]=i; add=n; memset(vis,0,sizeof(vis)); } int Find(int x) { return x==a[x]? x:a[x]=Find(a[x]); } void Unite(int x,int y) //入口由b[N]控制 { x=Find(x),y=Find(y); a[x]=y; } void Remove(int x) { a[add]=add,b[x]=add; add++; //金蝉脱壳 } int main() { while(cin>>n>>m) { init(); while(m--) { char op;int x,y; cin>>op; if(op==‘U‘) { cin>>x>>y; Unite(b[x],b[y]); } else { cin>>x; Remove(x); } } int ans=0; for(int i=0;i<n;i++) { if(!vis[Find(b[i])]) ans++,vis[Find(i)]=1; } printf("Case #%d: %d\n",++kase,ans); } }
nyoj_1022:合纵连横(并查集删点)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。