NC14521. 珂朵莉的无向图
描述
输入描述
第一行三个数表示n，m，q
之后m行每行两个数u，v表示有一条边位于u和v两个点之间
之后 2 x q 行表示询问
每次询问先输入两个数t，s
之后一行t个数，表示t个特殊点
输出描述
q行，每行一个数表示答案
示例1
输入:
5 6 6 2 3 1 3 2 5 1 3 3 2 2 5 1 1 3 1 1 1 1 4 1 1 2 5 1 4 1 1 4 5
输出:
3 2 4 3 4 4
说明:
n，m，q<= 5000 ,t的和<= 500000, s <= 109C++14(g++5.4) 解法, 执行用时: 616ms, 内存消耗: 3180K, 提交时间: 2020-05-12 14:16:49
#include<bits/stdc++.h>
using namespace std;
struct node
{
int x,h;
}Q[5005];
vector<int>R[5005];
bool V[5005];
int main()
{
int i,j,t,s,n,m,q,x,h,r,f,ans;
scanf("%d%d%d",&n,&m,&q);
while(m--)scanf("%d%d",&i,&j),R[i].push_back(j),R[j].push_back(i);
while(q--)
{
scanf("%d%d",&t,&s);
memset(V,0,sizeof(V)),ans=r=f=0;
while(t--)
{
scanf("%d",&i);
if(!V[i])V[i]=1,ans++,Q[r].x=i,Q[r++].h=0;
}
while(r!=f)
{
x=Q[f].x,h=Q[f++].h;
for(i=0;i<R[x].size();i++)
{
j=R[x][i];
if(h+1<=s&&!V[j])V[j]=1,ans++,Q[r].x=j,Q[r++].h=h+1;
}
}
printf("%d\n",ans);
}
return 0;
}