3. 染色问题
题目ID：20712必做题100分
最新提交：
Time Limit Exceeded
33 分
历史最高：
Time Limit Exceeded
33 分
时间限制: 1000ms
空间限制: 135536kB
题目描述
给定一张 NN 个点（编号为 1∼N1∼N），MM 条边的无向图，保证无重边无自环。现在有 KK 个被标记的点，其中第 ii 个被标记的点的编号为 pipi，任何从 pipi 出发经过不超过 hihi 条边能到达的点都会被染色（包括 pipi 自身）。你需要求出这张图最终有哪些点被染色。
输入格式
第一行三个正整数 N,M,KN,M,K，含义见题目描述。
接下来 MM 行，每行两个正整数 ai,biai,bi，表示编号为 ai,biai,bi 的点连有一条无向边。
接下来 KK 行，每行两个正整数 pi,hipi,hi，含义见题目描述。输出格式
第一行一个数字 GG，表示被染色的点的个数。
第二行 GG 个数字，表示被染色的点，按照从小到大的顺序输出。样例
Input 1
5 5 2 1 2 2 3 2 4 3 5 1 5 1 1 5 2
Output 1
4 1 2 3 5
Input 2
3 0 1 2 3
Output 2
1 2
Input 3
10 10 2 2 1 5 1 6 1 2 4 2 5 2 10 8 5 8 6 9 6 7 9 3 4 8 2
Output 3
7 1 2 3 5 6 8 9
数据范围
1≤N≤2×1051≤N≤2×105，0≤M≤2×1050≤M≤2×105，1≤K,ai,bi,pi,hi≤N1≤K,ai,bi,pi,hi≤N，pipi 互不相同。
保证给定的图无重边，无自环。
代码:
#include<bits/stdc++.h>
using namespace std;
int n,m,k;
vector<int> vec[200005];
struct box{
int x,d;
};
bool usevis[200005];
int cnt;
void bfs(int p,int h){
bool vis[200005]={0};
queue<box> que;
que.push({p,0});
vis[p]=1;
usevis[p]=1;
while(!que.empty()){
box tp=que.front();
que.pop();
if(tp.x==h){
continue;
}
for(auto i:vec[tp.x]){
if(vis[i]){
continue;
}
vis[i]=1;
usevis[i]=1;
que.push({i,tp.d+1});
}
}
}
int main(){
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<=m;i++){
int u,v;
scanf("%d%d",&u,&v);
vec[u].push_back(v);
vec[v].push_back(u);
}
while(k--){
int p,h;
scanf("%d%d",&p,&h);
bfs(p,h);
}
cout<<cnt<<endl;
for(int i=1;i<=n;i++){
if(usevis[i]){
cnt++;
}
}
cout<<cnt<<endl;
for(int i=1;i<=n;i++){
if(usevis[i]){
cout<<i<<" ";
}
}
return 0;
}