http://www.lydsy.com/JudgeOnline/problem.php?id=3237 (题目链接)

题意

  给出一个无向图,$Q$组询问,每次询问将原图断掉$C$条边后是否还连通。

Solution

  CDQ图分治,并查集维护。实在写不动题了,我能说我是蒯的吗T_T:http://blog.csdn.net/creationaugust/article/details/50889351

细节

  bzoj的G++版本是多久以前的了,莫名CE。。

代码

// bzoj3237
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<cmath>
#define LL long long
#define inf 2147483640
#define Pi acos(-1.0)
#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);
using namespace std; const int maxn=200010,maxm=5000010;
int ans[maxn],del[maxn],fa[maxn],st[maxm];
int n,m,Q,tim,top;
struct data {int c,id,e[4];}q[maxn];
struct edge {int u,v;}e[maxn]; namespace Unionset {
int find(int x) {
if (fa[x]==x) return x;
st[++top]=x;st[++top]=fa[x];return fa[x]=find(fa[x]);
}
void Union(int u,int v) {
if (find(u)!=find(v)) {
st[++top]=fa[v];
st[++top]=fa[fa[v]];
fa[fa[v]]=fa[u];
}
}
}
using namespace Unionset; void solve(int l,int r) {
int now=top,mid=(l+r)>>1,flag=1;
if (l==r) {
for (int i=0;i<q[l].c && flag;i++)
if (find(e[q[l].e[i]].u)!=find(e[q[l].e[i]].v)) flag=0;
ans[q[l].id]=flag;
for (;now!=top;top-=2) fa[st[top-1]]=st[top];
return;
}
tim++;
for (int i=l;i<=mid;i++)
for (int j=0;j<q[i].c;j++) del[q[i].e[j]]=tim;
for (int i=mid+1;i<=r;i++)
for (int j=0;j<q[i].c;j++)
if (del[q[i].e[j]]!=tim) Union(e[q[i].e[j]].u,e[q[i].e[j]].v);
solve(l,mid);tim++;
for (;now!=top;top-=2) fa[st[top-1]]=st[top];
for (int i=mid+1;i<=r;i++)
for (int j=0;j<q[i].c;j++) del[q[i].e[j]]=tim;
for (int i=l;i<=mid;i++)
for (int j=0;j<q[i].c;j++)
if (del[q[i].e[j]]!=tim) Union(e[q[i].e[j]].u,e[q[i].e[j]].v);
solve(mid+1,r);
for (;now!=top;top-=2) fa[st[top-1]]=st[top];
} int main() {
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++) fa[i]=i;
for (int i=1;i<=m;i++) scanf("%d%d",&e[i].u,&e[i].v);
scanf("%d",&Q);tim=1;
for (int i=1;i<=Q;i++) {
scanf("%d",&q[i].c);q[i].id=i;
for (int j=0;j<q[i].c;j++) scanf("%d",&q[i].e[j]),del[q[i].e[j]]=tim;
}
for (int i=1;i<=m;i++) if (del[i]!=tim) Union(e[i].u,e[i].v);
solve(1,Q);
for (int i=1;i<=Q;i++) puts(ans[i] ? "Connected" : "Disconnected");
return 0;
}

最新文章

  1. WIN32 窗口封装类实现
  2. Struts2中的ModelDriven机制及其运用
  3. Struts2中上传图片案列
  4. 新浪微博之XSS蠕虫脚本源码讲解
  5. 借助LVS+Keepalived实现负载均衡(转)
  6. Android Studio使用技巧
  7. 编写Windows Service 备忘
  8. webpackage 2.x 使用
  9. 关于Java String 类型转换时null的问题
  10. Photos_2017 China MVP Community Connection
  11. Android Tools&amp;Cmd
  12. 2004 ACM 成绩转换 两种方法
  13. 使用promise 和 generator来管理工作流
  14. java byte转string 涉及到字节流中有中文
  15. 行为型设计模式之模板方法(TEMPLATE METHOD)模式 ,策略(Strategy )模式
  16. FIO_工具_专业
  17. Intent----android中的伟大邮差
  18. 你真的了解[super ]关键字吗?
  19. centos配置DNS和ip
  20. 一直加载&ldquo;fonts.googleapis.com&rdquo;的解决办法

热门文章

  1. 手机app测试讲座
  2. 20155203 杜可欣《网络对抗技术》Exp1 PC平台逆向破解
  3. QTableWidget 详细使用
  4. 洛咕 P2336 [SCOI2012]喵星球上的点名
  5. SQL调优日志--内存问题排查入门篇
  6. Arcengine效率探究之一——属性的读取(转载)
  7. PAT甲题题解-1046. Shortest Distance (20)-做了一个假的最短路,水
  8. LeetCode 551. Student Attendance Record I (C++)
  9. linux内核分析第三周
  10. [转载]ValidationExpression验证规则