fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int INF = 1e9;
  5. const int MAX_N = 100005;
  6.  
  7. vector<int> g[MAX_N];
  8. int don[MAX_N], vis[MAX_N];
  9.  
  10. int bfs(int r) {
  11. 	queue<pair<int, int>> q;
  12. 	q.push({r, 0});
  13. 	vis[r] = r;
  14. 	while(!q.empty()) {
  15. 		int u, d;
  16. 		tie(u, d) = q.front();
  17. 		if(u!=r && don[u])
  18. 			break;
  19. 		q.pop();
  20. 		for(int v : g[u])
  21. 			if(vis[v]!=r)
  22. 				q.push({v, d+1}), vis[v] = r;
  23. 	}
  24. 	return q.front().second;
  25. }
  26.  
  27. int bfs1(int r, int mxd) {
  28. 	queue<pair<int, int>> q;
  29. 	q.push({r, 0});
  30. 	vis[r] = r;
  31. 	int c = 0;
  32. 	while(!q.empty()) {
  33. 		int u, d;
  34. 		tie(u, d) = q.front();
  35. 		if(d>mxd)
  36. 			break;
  37. 		q.pop();
  38. 		c++;
  39. 		for(int v : g[u])
  40. 			if(vis[v]!=r)
  41. 				q.push({v, d+1}), vis[v] = r;
  42. 	}
  43. 	return c;
  44. }
  45.  
  46. int main() {
  47. 	ios_base::sync_with_stdio(false);
  48. 	cin.tie(NULL);
  49.  
  50. 	int N, M, K;
  51. 	cin >> N >> M >> K;
  52. 	for(int i=0; i<M; i++) {
  53. 		int u, v;
  54. 		cin >> u >> v;
  55. 		g[u].push_back(v);
  56. 		g[v].push_back(u);
  57. 	}
  58. 	memset(don, 0, sizeof don);
  59. 	for(int i=0; i<K; i++) {
  60. 		int u;
  61. 		cin >> u;
  62. 		don[u] = 1;
  63. 	}
  64.  
  65. 	if(K==1) {
  66. 		cout << N << "\n";
  67. 		return 0;
  68. 	}
  69.  
  70. 	int dd = INF;
  71. 	memset(vis, 0, sizeof vis);
  72. 	for(int u=1; u<=N; u++)
  73. 		if(don[u])
  74. 			dd = min(dd, bfs(u));
  75. 	dd = (dd-1)/2;
  76.  
  77. 	int ans = 0;
  78. 	memset(vis, 0, sizeof vis);
  79. 	for(int u=1; u<=N; u++)
  80. 		if(don[u])
  81. 			ans += bfs1(u, dd);
  82.  
  83. 	cout << ans << "\n";
  84.  
  85. 	return 0;
  86. }
Success #stdin #stdout 0s 19192KB
comments (?)
stdin
copy 
5 4 2
1 2
2 3
3 4
4 5
1 5
stdout
copy 
4
https://ideone.com/p4YCpc
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
secret

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!