【dfs】bzoj3563 DZY Loves Chinese
2024-09-05 04:06:02
因为我们可以通过把某一行读到末尾来获取真正的K,所以把它和假K异或之后就是之前联通的次数(异或的逆运算为其本身)。最后一次的暴力一下。
#include<cstdio>
#include<cstring>
using namespace std;
#define N 100001
#define M 500001
int n,m,K,q,ans;
char s[1001];
bool del[M<<1];
int en,v[M<<1],first[N],next[M<<1],bs[20];
void AddEdge(int U,int V)
{
v[++en]=V;
next[en]=first[U];
first[U]=en;
}
bool vis[N];
int cnt,RealK;
void dfs(int U)
{
vis[U]=1; ++cnt;
for(int i=first[U];i;i=next[i])
if((!vis[v[i]])&&(!del[i]))
dfs(v[i]);
}
int main()
{
int A,B;
scanf("%d%d",&n,&m);
for(int i=1;i<=m;++i)
{
scanf("%d%d",&A,&B);
AddEdge(A,B);
AddEdge(B,A);
}
scanf("%d",&q);
for(int i=1;i<q;++i)
{
scanf("%d",&K);
RealK=0;
gets(s);
int len=strlen(s);
for(int j=0;j<len;++j)
if(s[j]==' ')
++RealK;
if(i!=1)
{
if((K^RealK)>ans) puts("Connected");
else puts("Disconnected");
}
ans=(K^RealK);
}
scanf("%d",&K);
RealK=0;
while(scanf("%d",&bs[++RealK])!=EOF);
if((K^(RealK-1))>ans) puts("Connected");
else puts("Disconnected");
ans=(K^(RealK-1));
for(int i=1;i<RealK;++i)
del[((bs[i]^ans)<<1)-1]=del[(bs[i]^ans)<<1]=1;
dfs(1);
puts(cnt==n?"Connected":"Disconnected");
return 0;
}
最新文章
- Python JPype 在 Win7 下安装与使用
- Android自定义View之倒计时Countdown实现
- Android使用Drawable资源之使用ClipDrawable资源 实现进入条
- C#:安装Windows服务,动态指定服务名及描述
- 【No.2 Ionic】Android打包
- $.extend,$.fn.extend,$.fn的区别
- Unity5 Standard自发光材质无效解决方法
- 光流算法:Brox光流的OpenCV源码解析
- 证书,CSP与Openssl
- PHP扩展高性能日志系统SeasLog简单上手
- 第一章04:JDK与JRE 区别
- Python练习一
- eclipse经常出现——未响应!!!
- Python写日志
- AC1000纪念
- JDK源码分析(一)——ArrayList
- 编译sass,遇到报错error style.scss (Line 3: Invalid GBK character ";\xE5";)
- 操作dict时避免出现KeyError的几种方法
- jvm2
- hdu 1848(Fibonacci again and again)(SG博弈)