3237: [Ahoi2013]连通图

Time Limit: 20 Sec  Memory Limit: 512 MB
Submit: 1736  Solved: 655
[Submit][Status][Discuss]

Description

Input

Output

Sample Input

4 5
1 2
2 3
3 4
4 1
2 4
3
1 5
2 2 3
2 1 2

Sample Output

Connected
Disconnected
Connected

HINT

N<=100000 M<=200000 K<=100000

Source

 

[Submit][Status][Discuss]

在线LCT,离线CDQ。

考虑怎么使用CDQ,对于区间[L,R],先将不在[L,mid]而在[mid+1,R]中的边加入,递归到左半边,撤销,将不在[mid+1,R]而在[L,mid]中的边加入,再次递归,撤销。

一般带撤销并查集是不能路径压缩的,但其实压缩了也没关系,记录压缩之前的父亲就好。

 #include<cstdio>
#include<cstring>
#include<algorithm>
#define rep(i,l,r) for (int i=l; i<=r; i++)
typedef long long ll;
using namespace std; const int N=,M=;
struct P{ int u,v,tim; }e[N];
struct Q{ int c[],cnt; }q[N];
int top,n,m,T,tim,u,v,f[N],ans[N],stk1[M],stk2[M]; int find(int x){
if (f[x]==x) return x;
int y=find(f[x]);
if (y!=f[x]) stk1[++top]=x,stk2[top]=f[x],f[x]=y;
return y;
} void solve(int l,int r){
int Top=top;
if (l==r){
int flag=;
rep(i,,q[l].cnt)
if (find(e[q[l].c[i]].u)!=find(e[q[l].c[i]].v))
{ flag=; break; }
ans[l]=flag;
while (top!=Top) f[stk1[top]]=stk2[top],top--;
return;
}
int mid=(l+r)>>; tim++;
rep(i,l,mid) rep(j,,q[i].cnt) e[q[i].c[j]].tim=tim;
rep(i,mid+,r) rep(j,,q[i].cnt){
int x=q[i].c[j];
if (e[x].tim!=tim){
int u=find(e[x].u),v=find(e[x].v);
if (u!=v) stk1[++top]=u,stk2[top]=f[u],f[u]=v;
}
}
solve(l,mid); tim++;
while (top!=Top) f[stk1[top]]=stk2[top],top--;
rep(i,mid+,r) rep(j,,q[i].cnt) e[q[i].c[j]].tim=tim;
rep(i,l,mid) rep(j,,q[i].cnt){
int x=q[i].c[j];
if (e[x].tim!=tim){
int u=find(e[x].u),v=find(e[x].v);
if (u!=v) stk1[++top]=u,stk2[top]=f[u],f[u]=v;
}
}
solve(mid+,r);
} int main(){
freopen("bzoj3237.in","r",stdin);
freopen("bzoj3237.out","w",stdout);
scanf("%d%d",&n,&m); tim=;
rep(i,,m) scanf("%d%d",&e[i].u,&e[i].v);
scanf("%d",&T);
rep(i,,T){
scanf("%d",&q[i].cnt); int x;
rep(j,,q[i].cnt) scanf("%d",&x),q[i].c[j]=x,e[x].tim=tim;
}
rep(i,,n) f[i]=i;
rep(i,,m) if (e[i].tim!=tim){
int u=find(e[i].u),v=find(e[i].v);
if (u!=v) f[u]=v;
}
solve(,T);
rep(i,,T) if (ans[i]) puts("Connected"); else puts("Disconnected");
return ;
}

最新文章

  1. SQL Server 数据库巡检脚本
  2. Linux安装时内存如何分区的相关问题
  3. codeforces 361 A - Mike and Cellphone
  4. javaSE第二十二天
  5. WPF 皮肤之MathApps.Metro UI库
  6. [App]华为P6设置与Xamarin Studio连通测试
  7. C#设置程序自启动
  8. ios9基础知识(技能篇)
  9. http://qt-project.org/wiki/Category:Developing_with_Qt::QtWebKit#ff7c0fcd6a31e735a61c001f75426961
  10. Crossin-8-1;8-2课程记录
  11. poj 1155 TELE(树形DP)
  12. 记Javascript的编写方式的全新学习
  13. jsp中的tag与tld
  14. [转]MYSQL 创建存储过程
  15. Gitlab迁移之数据库报错解决
  16. Kali学习笔记5:被动信息收集工具集
  17. leetcode刷题--两数之和(简单)
  18. HTML轮播图实现(前后端分离)
  19. 419. Battleships in a Board 棋盘上的战舰数量
  20. Mac 安装zsh

热门文章

  1. BigDecimal简单说
  2. ASP.NET Core [2]:Middleware-请求管道的构成(笔记)
  3. Windows批处理中获取日期和时间
  4. 1155 Heap Paths (30 分)(堆+dfs遍历)
  5. css深入理解vertical-align
  6. HDU 4455 Substrings ( DP好题 )
  7. 【bzoj2044】三维导弹拦截 dp+二分图最大匹配
  8. BZOJ 1208 [HNOI2004]宠物收养所 | SPlay模板题
  9. BZOJ4824 [Cqoi2017]老C的键盘 【树形dp】
  10. bzoj1264 [AHOI2006]基因匹配Match 树状数组+lcs