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. 	 while(!q.empty())
  29. 	  {
  30. 	  	int removed;
  31. 	  	removed=q.front();
  32. 	  	q.pop();
  33.  
  34. 	  	for(auto x:b[removed])
  35. 	  	 {
  36. 	  	 	if(used[x]==0)
  37. 	  	 	 {
  38. 	  	 	 	q.push(x);
  39. 	  	 	 	used[x]=1;
  40. 	  	 	 	level[x]=level[removed]+1;
  41. 	  	 	 	ways[x]=ways[removed];
  42. 	  	 	 }
  43. 	  	 	  else
  44. 	  	  	  {
  45. 	  	  	  	if(level[x]==level[removed]+1)
  46. 	  	  	  	 {
  47. 	  	  	  	   ways[x]=ways[x]+ways[removed];	
  48. 	  	  	  	 }
  49.  
  50. 	  	  	  }
  51. 	  	 }
  52.  
  53.  
  54. 	  }
  55.  
  56.  
  57.  
  58.  
  59.  
  60. 	  //		  i=1;
  61. 	  //while(i<=n)
  62. 	  // {
  63. 	  // 	cout<<"the no of ways to reach "<<i<<" to "<<"source node is "<<ways[i]<<" "<<endl;
  64. 	  // 	i++;
  65. 	  // }
  66.  
  67. 	   cout<<ways[6];
  68.  
  69.  
  70.  
  71.  
  72.  
  73. 	return 0;
  74. }
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
6 6
1 2
1 3
2 4
3 5
4 6 
5 6
stdout
copy 
2
https://ideone.com/E5xqy9
language:
C++ (gcc 8.3)
created:
2 days 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!