fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. bool don[100000];
  4. bool visited[100000];
  5. int radius[100000];
  6. int r=1000000;
  7. vector< vector<int> > graph(100000);
  8. void dfs(int u){
  9.     for(int i=0;i<graph[u].size();i++){
  10.         int v=graph[u][i];
  11.         if(!visited[v]){
  12.             if(!don[v]){
  13.                 radius[v]=radius[u]+1;
  14.                 visited[v]=true;
  15.                 dfs(v);
  16.             }
  17.             else{
  18.                 r=min(r,radius[u]/2);
  19.             }
  20.         } 
  21.     }
  22. }
  23.  
  24. void dfs2(int u){
  25.     for(int i=0;i<graph[u].size();i++){
  26.         int v=graph[u][i];
  27.         if(!visited[v]){
  28.             if(r<radius[u]+1) continue;
  29.             radius[v]=radius[u]+1;
  30.             visited[v]=true;
  31.             dfs2(v);
  32.         } 
  33.     }
  34. }
  35.  
  36. int main() {
  37.     int n,m,k,x,y;
  38.     scanf("%d%d%d",&n,&m,&k);
  39.     while(m--){
  40.         scanf("%d%d",&x,&y);
  41.         graph[x-1].push_back(y-1);
  42.         graph[y-1].push_back(x-1);
  43.     }    
  44.     for(int i=0;i<k;i++){
  45.         scanf("%d",&x);
  46.         don[x-1]=true;
  47.     }
  48.     for(int i=0;i<n;i++){
  49.         if(don[i]){
  50.             visited[i]=true;
  51.             radius[i]=0;
  52.             dfs(i);
  53.         }
  54.     }
  55.     for(int i=0;i<n;i++) visited[i]=false;
  56.     int count=0;
  57.     for(int i=0;i<n;i++){
  58.         if(don[i]){
  59.             radius[i]=0;
  60.             visited[i]=true;
  61.             dfs2(i);
  62.         }
  63.     }
  64.     for(int i=0;i<n;i++){
  65.         if(visited[i]) count++;
  66.     }
  67.     printf("%d",count);
  68. 	return 0;
  69. }
Success #stdin #stdout 0s 15824KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/F6NfKX
language:
C++14 (clang 8.0)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!