UESTC 1811 Hero Saving Princess - c++编程基础

题意：T个测试数据

n m //n个点 m条边

m条无向边

que//下面有que个数据

a b // 表示a点的钥匙在b中

问，从0点开始能否遍历所有的点

思路：用BFS搜一遍即可，注意图是否连通，用并查集判断一下

BFS()时，q为正常队列，p为走到那个点是锁住时将q中点移到p中

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define inf 1073741824
#define N 100100
#define ll int
using namespace std;
inline ll Max(ll a,ll b){return a>b a:b;}

int lock[N],key[N],n,m;//lock=0表示没锁 ,key[i] 表示i房间中的钥匙，没有钥匙=-1
vectorG[N];
queueq,p;//q表示bfs的没锁的点，p表示被锁的点

int f[N];
int find(int x){
	if(f[x]==x)return x;
	return f[x]=find(f[x]);
}

bool vis[N],inp[N];

void BFS(){
	memset(vis,0,sizeof(vis));
	memset(inp,0,sizeof(inp));
	q.push(0);
	vis[0]=true;
	int i,v,u,len;
	bool change=true;

	while(1)
	{
		change=false;//跳出条件是有新的点可以走
		while(!q.empty())
		{
			u=q.front(); q.pop();
			len=G[u].size();
			for(i=0;i




=0) //u点没有锁
					q.push(u),vis[u]=true;
				else p.push(u);				
			}
		}

	}
}

int main(){
	int i,j,a,b,que;
	int T,Cas=1;scanf("%d",&T);

	while(T--){
		memset(lock,0,sizeof(lock));
		memset(key,-1,sizeof(key));
		scanf("%d%d",&n,&m);
		for(i=0;i