【题目分析】

腊鸡题目卡题面。

大概的意思就是给一张无向图,每次删掉其中一些边,问是否联通。

首先想到的是Bitset,可以做到n^2/64。显然过不了。

然而这是lyd在给我们讲线性基的时候的一道题目。↓

首先构建dfs树。

发现图不联通的时候,当且仅当删去了树边和所有覆盖它的非树边。

所以对于每一条非树边随机一个权值,然后每条树边为所有覆盖它的非树边的权值的异或。

每次判断是否线性无关即可。

神题!

【代码】

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath> #include <set>
#include <map>
#include <string>
#include <algorithm>
#include <vector>
#include <iostream>
#include <queue> using namespace std; #define maxn 100005
#define maxm 1000005
#define mxle 65
#define ll long long
#define F(i,j,k) for (int i=j;i<=k;++i)
#define D(i,j,k) for (int i=j;i>=k;--i)
#define inf (0x3f3f3f3f) void Finout()
{
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
#endif
} int Getint()
{
int x=0,f=1; char ch=getchar();
while (ch<'0'||ch>'9') {if (ch=='-') f=-1; ch=getchar();}
while (ch>='0'&&ch<='9') {x=x*10+ch-'0'; ch=getchar();}
return x*f;
} vector <int> v[maxn];
int h[maxm],fr[maxm],to[maxm],ne[maxm],en=0,f[maxn],tag[maxm];
int w[maxm],b[maxm];
int vis[maxm]; void add(int a,int b)
{
fr[en]=a; to[en]=b; ne[en]=h[a]; h[a]=en++;
fr[en]=b; to[en]=a; ne[en]=h[b]; h[b]=en++;
} void dfs1(int o,int fa)
{
vis[o]=1;
for (int i=h[o];i>=0;i=ne[i])
{
if (!vis[to[i]]) dfs1(to[i],o);
else if (!w[i]&&to[i]!=fa)
{
w[i]=w[i^1]=rand()*711;
b[o]^=w[i]; b[to[i]]^=w[i];
}
}
} int n,m; void dfs2(int o)
{
vis[o]=1;
for (int i=h[o];i>=0;i=ne[i])
{
if (!vis[to[i]])
{
dfs2(to[i]);
w[i]=w[i^1]=b[to[i]];
b[o]^=b[to[i]];
}
}
} struct Base{
int lb[mxle];
bool add(int x)
{
D(i,30,0)
{
if ((x>>i)&1)
{
if (!lb[i]) {lb[i]=x;return false;}
else x^=lb[i];
}
}
return true;
}
void init(int x){memset(lb,0,sizeof lb);add(x);}
}bas; int q,x,y; int main()
{
memset(h,-1,sizeof h);
srand(20000416);
Finout();
n=Getint();m=Getint();
F(i,1,m) add(Getint(),Getint());
dfs1(1,0);
memset(vis,0,sizeof vis);
dfs2(1);
int ans=0,flag=0;
q=Getint();
F(i,1,q)
{
flag=0;
x=Getint(); bas.init(0);
F(i,1,x)
{
y=Getint(); y^=ans;
if (bas.add(w[2*y-1])) flag=1;
}
flag^=1;
if (flag) printf("Connected\n");
else printf("Disconnected\n");
ans+=flag;
}
}

  

最新文章

  1. MongoDB 安装
  2. 系统进程 zygote(二)—— zygote.rc 脚本
  3. fil_space_t
  4. 用js实现选项卡切换效果
  5. mac上SVN项目管理,提示被锁定的解决方法
  6. bzoj1878
  7. RPM工具
  8. php 图片上传预览(转)
  9. VS2010/MFC对话框:向导对话框的创建及显示
  10. wuzhicms 数据迁移策略
  11. 解题报告8VC Venture Cup 2017 - Elimination Round
  12. Erlang cowboy websocket 服务器
  13. 【LeetCode】89.Gary Code
  14. 微信小程序如何套用iconfont
  15. HttpRunner框架(一)
  16. DB2 rollforward 命令使用详解
  17. 原来 php 中的 json_encode() 只支持utf-8.不支持gbk啊
  18. PAT甲题题解-1069. The Black Hole of Numbers (20)-模拟
  19. Eclipse SDK Android Studio 下载地址
  20. 在Win7 Hyper-v虚拟机中挂接真实机的声卡

热门文章

  1. Microsoft Sql server2005的安装步骤和常见问题解决方案
  2. linux虚拟机安装值得注意的几点
  3. Bootstrap历练实例:响应式导航栏
  4. kafka启动报错&amp;问题解决
  5. shell脚本,计算学生分数的题目。
  6. 第五次作业:Excel制作英文课程表
  7. iOS开发--使用OpenSSL生成私钥和公钥的方法
  8. C++系统学习之六:函数
  9. linux各种终端类型的区别和概念
  10. 如何用纯 CSS 创作一个雷达扫描动画