全体集合

NC232001. 全体集合

描述

给出 $n$ 个点 $m$ 条边的无向图，给出 $k$ 个点，这 $k$ 个点上每个点都有一个人，每个人每回合能走到一个相邻的节点（不能停留不走），问：有没有可能在某一个回合，让这些人都集中在一个点？

输入描述

第一行包含三个整数 $n$ $m$ $k$ ， $1\le n,k\le 2e5$ ， $0\le m\le min(5e5,n*(n-1)/2)$ 。

接下来 $m$ 行，每行包括两个整数 $u$ $v$ ，表示存在一条从节点 $u$ 到 $v$ 的边，节点编号从 $1$ 开始，保证图联通，无重边，无自环。

接下来一行，包含 $k$ 个整数，分别表示有人所在的节点，保证 $k$ 个节点各不相同。

输出描述

输出包括一行，如果有办法能让全部人都集中在一个点，输出”YES“，否则输出”NO“，不包含引号。

示例1

输入:

输出:

YES

说明:

第一回合，让节点 $1$ 的人走到节点 $2$ ，节点 $3$ 的人走到节点 $2$ ，全都集中了，输出YES。

示例2

输入:

输出:

NO

说明:

由于每回合不能不移动，不存在一种走法让全部人集中。

原站题解

上次编辑到这里，代码来自缓存点击恢复默认模板

C++ 解法, 执行用时: 517ms, 内存消耗: 45604K, 提交时间: 2022-01-14 10:44:42

#include<bits/stdc++.h>
using namespace std;
int i,j,k,n,m,t,f[1005000],a[2];
vector<int> v[1005000];
void dfs(int x){
	for(auto i:v[x]){
		if(f[i]==-1){f[i]=f[x]^1;dfs(i);}
		else if(f[i]==f[x]){cout<<"YES";exit(0);}
	}
}
int main() {
	memset(f,-1,sizeof(f));
	cin>>n>>m>>t;
	for(i=1;i<=m;i++){
		cin>>j>>k;
		v[j].push_back(k);v[k].push_back(j);
	}
	f[1]=0;dfs(1);
	while(t--){cin>>k;a[f[k]]++;}
	cout<<((a[0]&&a[1])?"NO":"YES");
}

上一题

下一题

详情