首页 > 代码库 > BZOJ 3563 DZY Loves Chinese 并查集
BZOJ 3563 DZY Loves Chinese 并查集
题目大意:给定一个无向联通图,q次询问当图中某k条边消失时图是否联通 强制在线
逗比题233
不明白什么意思的去看DZY Loves Chinese II的红字就明白这题为何逗比了0.0
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define M 100100 using namespace std; struct edges{ int x,y; }e[500500]; int n,m,q,block; bool v[500500]; char s[1010]; int fa[M],ans[M]; int Find(int x) { if(!fa[x]||fa[x]==x) return fa[x]=x; return fa[x]=Find(fa[x]); } void Unite(int x,int y) { x=Find(x);y=Find(y); if(x==y) return ; fa[x]=y;block--; } int main() { int i,j,k,_k; cin>>n>>m; for(i=1;i<=m;i++) scanf("%d%d",&e[i].x,&e[i].y); cin>>q; for(i=1;i<=q;i++) { scanf("%d",&_k); gets(s+1);k=0; for(j=1;s[j];j++) if( isdigit(s[j]) && !isdigit(s[j+1]) ) ++k; ans[i]=k^_k; } for(i=1;i<q;i++) printf("%s\n",ans[i+1]-ans[i]?"Connected":"Disconnected"); int temp=0; for(i=1,s[0]='a';s[i-1];i++) { if( isdigit(s[i]) ) temp*=10,temp+=s[i]-'0'; else if( isdigit(s[i-1]) ) v[temp^ans[q]]=1,temp=0; } block=n; for(i=1;i<=m;i++) if(!v[i]) Unite(e[i].x,e[i].y); puts(block==1?"Connected":"Disconnected"); return 0; }
BZOJ 3563 DZY Loves Chinese 并查集
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。