C++(g++ 7.5.0) 解法, 执行用时: 273ms, 内存消耗: 25920K, 提交时间: 2022-08-25 19:44:33

#include <bits/stdc++.h>
using namespace std;
#define N 500005
int T, n, m, k, x, y, f[N];
queue<int> q;
vector <int> g[N];
bool v[N];
int main()
{
	scanf("%d", &T);
	while(T--)
	{
		scanf("%d%d%d", &n, &m, &k);
		for(int i = 1; i <= n; i++)
			g[i].clear();
		memset(f, 0, sizeof(f));
		memset(v, 0, sizeof(v));
		for(int i = 1; i <= k; i++)
		{
			scanf("%d", &x);
			q.push(x);
			v[x] = 1;
		}
		for(int i = 1; i <= m; i++)
		{
			scanf("%d%d", &x, &y);
			g[x].push_back(y);
			g[y].push_back(x);
		}
		while(!q.empty())
		{
			x = q.front();
			q.pop();
			for(int i = 0; i < g[x].size(); i++)
			{
				y = g[x][i];
				if(v[y])  continue;
				if(++f[y] >= 2)
				{
					v[y] = 1;
					q.push(y);
				}
			}
		}
		printf(v[1] ? "yes\n" : "no\n");
	}
	return 0;
}

C++ 解法, 执行用时: 228ms, 内存消耗: 24640K, 提交时间: 2021-12-04 18:42:31

#include<bits/stdc++.h>
using namespace std;

vector<int>R[500005];
int Q[500005],cnt[500005];
bool V[500005];
int main()
{
	int i,j,n,m,t,r,f,x,T;
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d%d%d",&n,&m,&t),r=f=0;
		for(i=1;i<=n;i++)R[i].clear(),cnt[i]=V[i]=0;
		while(t--)
		{
			scanf("%d",&x);
			V[x]=cnt[x]=1,Q[r++]=x;
		}
		while(m--)scanf("%d%d",&i,&j),R[i].push_back(j),R[j].push_back(i);
		while(r!=f)
		{
			x=Q[f++];
			for(i=0;i<R[x].size();i++)
			{
				j=R[x][i],cnt[j]++;
				if(cnt[j]>=2&&!V[j])V[j]=1,Q[r++]=j;
			}
		}
		if(V[1])puts("yes");
		else puts("no");
	}
    return 0;
}