fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define MOD 1000000007
  3. #define quick ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
  4. using namespace std;
  5. typedef long long ll;
  6. typedef long double ld;
  7.  
  8. vector<vector<ll> > graph;
  9. vector<ll> heights;
  10. vector<bool> visited;
  11.  
  12. ll bfs(ll s,ll f){
  13. 	deque<pair<ll,ll> > q;
  14. 	q.push_back(make_pair(f,0));
  15. 	visited[f]=true;
  16. 	while(!q.empty())
  17. 	{
  18. 		pair<ll,ll> curr=q.front();
  19. 		q.pop_front();
  20. 		if(curr.first<s)
  21. 		{
  22. 			heights.push_back(curr.second);
  23. 		}
  24. 		for(ll i=0;i<graph[curr.first].size();i++)
  25. 		{
  26. 			if(!visited[graph[curr.first][i]])
  27. 			{
  28. 				q.push_back(make_pair(graph[curr.first][i],curr.second+1));
  29. 				visited[graph[curr.first][i]]=true;
  30. 			}
  31. 		}
  32. 	}
  33. 	assert(heights.size()==s);
  34. 	sort(heights.begin(),heights.end());
  35. 	ll ans=1;
  36. 	for(ll i=heights.size()-2;i>=0;i--)
  37. 	{
  38. 		if(heights[i]==heights[i+1])
  39. 		{
  40. 			ans++;
  41. 		}
  42. 		else
  43. 			break;
  44. 	}
  45. 	return ans;
  46. }
  47. int main()
  48. {
  49. 	ll s,n,e;
  50. 	cin>>s>>n>>e;
  51. 	ll f=n-1;
  52. 	graph.resize(n);
  53. 	visited.resize(n);
  54. 	for(ll i=0;i<e;i++)
  55. 	{
  56. 		ll a,b;
  57. 		cin>>a>>b;
  58. 		a--;
  59. 		b--;
  60. 		graph[a].push_back(b);
  61. 		graph[b].push_back(a);
  62. 	}
  63. 	ll ans=bfs(s,f);
  64. 	cout<<ans<<endl;
  65. 	return 0;
  66. }
Success #stdin #stdout 0s 15248KB
comments (?)
stdin
copy 
3 5 4
1 5
2 4
3 4
5 4
stdout
copy 
2
https://ideone.com/qQTlg8
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!