[BZOJ3237][AHOI2013]连通图(分治并查集)
2024-09-02 20:56:23
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 2Sample Output
Connected
Disconnected
ConnectedHINT
N<=100000 M<=200000 K<=100000
Source
在线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 ;
}
最新文章
- SQL Server 数据库巡检脚本
- Linux安装时内存如何分区的相关问题
- codeforces 361 A - Mike and Cellphone
- javaSE第二十二天
- WPF 皮肤之MathApps.Metro UI库
- [App]华为P6设置与Xamarin Studio连通测试
- C#设置程序自启动
- ios9基础知识(技能篇)
- http://qt-project.org/wiki/Category:Developing_with_Qt::QtWebKit#ff7c0fcd6a31e735a61c001f75426961
- Crossin-8-1;8-2课程记录
- poj 1155 TELE(树形DP)
- 记Javascript的编写方式的全新学习
- jsp中的tag与tld
- [转]MYSQL 创建存储过程
- Gitlab迁移之数据库报错解决
- Kali学习笔记5:被动信息收集工具集
- leetcode刷题--两数之和(简单)
- HTML轮播图实现(前后端分离)
- 419. Battleships in a Board 棋盘上的战舰数量
- Mac 安装zsh
热门文章
- BigDecimal简单说
- ASP.NET Core [2]:Middleware-请求管道的构成(笔记)
- Windows批处理中获取日期和时间
- 1155 Heap Paths (30 分)(堆+dfs遍历)
- css深入理解vertical-align
- HDU 4455 Substrings ( DP好题 )
- 【bzoj2044】三维导弹拦截 dp+二分图最大匹配
- BZOJ 1208 [HNOI2004]宠物收养所 | SPlay模板题
- BZOJ4824 [Cqoi2017]老C的键盘 【树形dp】
- bzoj1264 [AHOI2006]基因匹配Match 树状数组+lcs