zoj 3509

zoj 3509题目大意:N个点,M次加边/删边/询问两点连通性操作,初始图为空。N题解:想什么呢,大力bitset!N*N*M/32花式水过!附代码:#include#defineN510usingnamespacestd;bitsets[N],ned,now,emp;intn,m;inlineboolquery(inta,intb){ ned=now=s[a

大家好,又见面了,我是你们的朋友全栈君。

题目大意:

N个点,M次加边/删边/询问两点连通性操作,初始图为空。N<=500,M<=50000,每条边最多加一次。

题解:

想什么呢,大力bitset!N*N*M/32花式水过!

附代码:

#include<bits/stdc++.h>
#define N 510
using namespace std;
bitset<N> s[N],ned,now,emp;
int n,m;
inline bool query(int a,int b){
	ned=now=s[a];ned[a]=0;
	int ta;
	while((ta=ned._Find_first())!=N){
		ned[ta]=0;
		ned|=(now|s[ta])^now;
		now|=s[ta];
		if(now[b]) return 1;
	}
	return now[b];
}
int main(){
	char ch[5];int a,b;
	int tot=0;
	while(~scanf("%d%d",&n,&m)){
		if(tot) puts("");
		for(int i=0;i<n;i++){
			s[i]=emp;
			s[i][i]=1;
		}
		printf("Case %d:\n",++tot);
		while(m--){
			scanf("%s%d%d",ch,&a,&b);
			a--,b--;
			if(ch[0]=='I') s[a][b]=s[b][a]=1;
			else if(ch[0]=='D') s[a][b]=s[b][a]=0;
			else{
				if(a==b) puts("YES");
				else if(query(a,b)) puts("YES");
				else puts("NO");
			}
		}
	}
	return 0;
}

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/158017.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号