fork download
copy 
  1. #include <iostream>
  2. using namespace std;
  3. #include <bits/stdc++.h>
  4.  
  5. int main() {
  6. 	// your code goes here
  7. 	int n,m;
  8. 	cin>>n>>m;
  9. 	vector<int>b[n+5];
  10. 	int i=1;
  11. 	for(i=1;i<=m;i++)
  12. 	 {
  13. 	 	int x,y;
  14. 	 	cin>>x>>y;
  15. 	 	b[x].push_back(y);
  16. 	 	b[y].push_back(x);
  17. 	 }
  18.  
  19. 	 int source = 1;
  20. 	 int used[n+5]={0};
  21. 	 int level[n+5]={-1};
  22. 	 queue<int>q;
  23. 	 q.push(source);
  24. 	 used[source]=1;
  25. 	 level[source]=0;
  26. 	 int ways[n+5]={0};
  27. 	 ways[1]=1;
  28. 	 int count=0;
  29. 	 //int count[n+5]={0};
  30. 	 while(!q.empty())
  31. 	  {
  32. 	  	int removed;
  33. 	  	removed=q.front();
  34. 	   //cout<<removed<<"-"<<count<<endl;
  35. 	  	q.pop();
  36.  
  37.  
  38. 	  	for(auto x:b[removed])
  39. 	  	 {
  40. 	  	 	if(used[x]==0)
  41. 	  	 	 {
  42.  
  43. 	  	 	 	q.push(x);
  44. 	  	 	 	used[x]=1;
  45. 	  	 	 	level[x]=level[removed]+1;
  46. 	  	 	 	if(x==5)
  47. 	  	 	 	 {
  48. 	  	 	 	 	ways[x]=count++;
  49.  
  50. 	  	 	 	 }else
  51. 	  	 	 	 {
  52. 	  	 	 	 	ways[x]=ways[removed]+ways[x];
  53. 	  	 	 	 }
  54.  
  55. 	  	 	 }
  56. 	  	 	  else
  57. 	  	  	  {
  58. 	  	  	  	if(level[x]==level[removed]+1)
  59. 	  	  	  	 {
  60. 	  	  	  	 	if(x==5)
  61. 	  	 	 	    {
  62. 	  	 	 	 	ways[x]=count++;
  63.  
  64. 	  	 	 	    }else
  65. 	  	 	 	     {
  66. 	  	 	 	 	  ways[x]=ways[removed]+ways[x];
  67. 	  	 	 	     }
  68. 	  	  	  }
  69. 	  	 }
  70. 	  	 }
  71.  
  72.  
  73. 	  }
  74.  
  75.  
  76.  
  77.  
  78.  
  79. 	  		  i=1;
  80. 	  while(i<=n)
  81. 	   {
  82. 	   	cout<<i<<"-"<<ways[i]<<endl;
  83. 	   	i++;
  84. 	   }
  85.  
  86. 	  // cout<<ways[6];
  87.  
  88.  
  89.  
  90.  
  91.  
  92. 	return 0;
  93. }
Success #stdin #stdout 0s 5284KB
comments (?)
stdin
copy 
8 8
0 5
0 5
5 5
5 0
5 0
0 0
0 0
0 0
stdout
copy 
1-1
2-0
3-0
4-0
5-0
6-0
7-0
8-0
https://ideone.com/ZQJe7D
language:
C++ (gcc 8.3)
created:
20 hours 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!