首页 > 代码库 > ZOJ 3811

ZOJ 3811

亏大了,当时没做,被另一道题目题意给坑了,其实把他建成一个双向图,首先l <k  或者整个图 无法连通 那么肯定是No,在这个双向图里,以 L 个触发器 亮的顺序来,先从第一个开始深搜,遇到一个触发器 就停止往下搜,这样 当前第一个触发器 与其它 几个触发器之间有路径可达,并放在一个集合里,接下来判断 第二个触发器是否在这个集合里,以此类推,到第二个触发器  也去深搜,搜完 再判断第三个触发器 是否在这个集合里推到最后一个即可,而且搜索过的点可以不用再搜索,降低了复杂度,因为若都在一个集合里,肯定是可以到达的,

看题解多数使用了并查集,不过也有几个题解的的思路 差不多也是这个样子,解法挺多的


int t;
int n,m,k;
int nnum[100000 + 55];
bool vis[100000 + 55];
bool flag[100000 + 55];

vector<int > G[100000 + 55];
set<int > my_set;

void init() {
	my_set.clear();
	memset(vis,false,sizeof(vis));
	memset(nnum,0,sizeof(nnum));
	memset(flag,false,sizeof(flag));
	for(int i=0;i<100000 + 55;i++)G[i].clear();
}

bool input() {
	while(scanf("%d %d %d",&n,&m,&k)) {
		int xx;
		for(int i=0;i<k;i++) scanf("%d",&xx);
		int q = m;
		while(q--) {
			int u,v;
			scanf("%d %d",&u,&v);
			G[u].push_back(v);
			G[v].push_back(u);
		}
		return false;
	}
	return true;
}

void dfs(int u) {
	vis[u] = true;
	for(int i=0;i<G[u].size();i++) {
		int v = G[u][i];
		if(!vis[v]) {
			if(flag[v]){ my_set.insert(v);continue;}
			dfs(v);
		}
	}
}

void cal() {
	int l;
	scanf("%d",&l);
	for(int i=0;i<l;i++) {
		scanf("%d",&nnum[i]);
		flag[nnum[i]] = true;
	}
	if(l < k){puts("No");return ;}
	dfs(nnum[0]);
	for(int i=1;i<l;i++) {
		if(my_set.find(nnum[i]) == my_set.end()) { puts("No");return ; }
		dfs(nnum[i]);
	}
	for(int i=1;i<=n;i++) {
		if(!vis[i]) {puts("No");return ;}
	}
	puts("Yes");
}

void output() {

}

int main() {
	scanf("%d",&t);
	while(t--) {
		init();
		if(input())return 0;
		cal();
		output();
	}
	return 0;
}



ZOJ 3811