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

cdq分治+缩点。

可以每次处理的时候把除l~r之外的边的端点都连起来。然后去跑cdq分治。

当l==r的时候让那些修改边不连然后跑一边并查集。

#include<cstring>
#include<iostream>
#include<algorithm>
#include<cstdio>
#define rep(i,l,r) for (int i=l;i<=r;i++)
#define down(i,l,r) for (int i=l;i>=r;i--)
#define clr(x,y) memset(x,y,sizeof(x))
#define maxn 200500
using namespace std;
struct data{int x,y,id,k,b;
}a[][maxn];
int b[maxn][];
int fa[maxn],np[maxn],pos[maxn],n,m,Q;
int read(){
int x=,f=; char ch=getchar();
while (!isdigit(ch)) {if (ch=='-') f=-; ch=getchar();}
while (isdigit(ch)) {x=x*+ch-''; ch=getchar();}
return x*f;
}
int find(int x){
if (fa[x]==x) return x;
return fa[x]=find(fa[x]);
}
void cdq(int dep,int l,int r,int n,int m){
rep(i,,m){
data &c=a[dep][i],&c2=a[dep-][i];
c=(data){c2.x,c2.y,c2.id,,};
pos[c2.id]=i;
}
if (l==r){
rep(i,,b[l][]) a[dep][pos[b[l][i]]].b=;
rep(i,,n) fa[i]=i;
int cnt=;
rep(i,,m) if (a[dep][i].b!=) {
data c=a[dep][i];
int x=find(c.x),y=find(c.y);
if (x!=y) fa[x]=y,cnt++;
}
if (cnt==n-) puts("Connected");
else puts("Disconnected");
return;
}
rep(i,l,r) rep(j,,b[i][]) a[dep][pos[b[i][j]]].k=;
rep(i,,n) fa[i]=i;
rep(i,,m) if (a[dep][i].k==){
data &c=a[dep][i];
int x=find(c.x),y=find(c.y);
if (x!=y) fa[x]=y;
}
rep(i,,n) np[i]=;
int nn=,nm=;
rep(i,,n) if (!np[find(i)]) np[find(i)]=++nn;
rep(i,,m) if (a[dep][i].k) {
data c=a[dep][i];
int x=find(c.x),y=find(c.y);
a[dep][++nm]=(data){np[x],np[y],c.id,c.k,};
}
int mid=(l+r)/;
cdq(dep+,l,mid,nn,nm);
cdq(dep+,mid+,r,nn,nm);
}
int main(){
n=read(); m=read();
int x,y;
rep(i,,m){
x=read(); y=read();
a[][i]=(data){x,y,i,,};
}
Q=read();
rep(i,,Q){
b[i][]=read();
rep(j,,b[i][]) b[i][j]=read();
}
cdq(,,Q,n,m);
return ;
}

最新文章

  1. js作用域
  2. iOS开发小技巧--利用苹果官方API播放视频(方法已经过时,了解一下)
  3. delphi TeeChart保存3种图片文件
  4. 常用经典SQL语句大全(提升)
  5. C++ 知识点 2
  6. ThinkPHP视图查询详解
  7. flask tutorial =&gt; make a blog :) flask 搭建博客系统从零开始!
  8. Linux系统上安装JDK1.8
  9. Windows7下chm文件打不开
  10. (三)初探maven之使用IDE
  11. Python3 tkinter基础 Radiobutton 创建三个单选钮
  12. Java面试之高并发系统
  13. CMakeLists.txt使用
  14. 2.node.js (二)服务器登录注册 与 包的发布
  15. Oracle课程档案,第六天
  16. 【Python全栈-后端开发】Django入门基础
  17. git reset 版本回退
  18. C语言中的 (void*)0 与 (void)0
  19. 开发openfire 消息拦截器插件PacketInterceptor
  20. Fedora归档管理器支持Rar、7Z

热门文章

  1. iOS 获取当前应用的信息以及用户信息:版本号手机号手机型号
  2. 免费SSL&amp;付费SSL证书,该如何选择?
  3. [置顶] Xamarin android 调用Web Api(ListView使用远程数据)
  4. bzoj 3996: [TJOI2015]线性代数
  5. SSH远程登录密码尝试
  6. 正则表达式与grep
  7. js、jQuery、layer实现弹出层的打开、关闭
  8. 解决SVN造成的桌面图标问号
  9. java juint框架的windows自动化-自动运行juint程序简述
  10. 前端之 HTML&#127875;