fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. class graph
  4. {
  5. 	int v;
  6. 	list<int> *adj;
  7. 	public:
  8. 	graph(int v)
  9. 	{
  10. 		this->v=v;
  11. 		adj=new list<int>[v];
  12. 	}
  13. 	void add_edge(int a,int b)
  14. 	{
  15. 	  adj[a].push_back(b);
  16. 	}
  17. 	void bfs(int start,bool visited[])
  18. 	{
  19. 		queue<int> q;
  20. 		q.push(start);
  21. 		visited[start]=true;
  22. 		list<int>::iterator it;
  23. 		for(it=adj[start].begin();it!=adj[start].end();++it)
  24. 		{
  25. 			if(!visited[*it]){
  26.  
  27. 			q.push(*it);
  28. 			visited[*it]=true;
  29. 			//note: always pass by address otherwise nothing will be added
  30. 			bfsUtil(*it,visited,&q);
  31. 			}
  32. 		}
  33.  
  34. 		while(q.size())
  35. 		{
  36. 			cout<<q.front()<<"->";
  37. 			q.pop();
  38. 		}
  39. 	}
  40. 	void bfsUtil(int start,bool visited[],queue<int> *q)
  41. 	{
  42.  
  43. 		list<int>::iterator it;
  44. 		for(it=adj[start].begin();it!=adj[start].end();++it)
  45. 		{
  46. 			if(!visited[*it]){
  47. 			(*q).push(*it);
  48. 		    visited[*it]=true;
  49. 			bfsUtil(*it,visited,q);
  50. 			}
  51. 		}
  52. 	}
  53. 	void bfsEachVertex()
  54. 	{
  55. 		queue<int> q[v];
  56. 		bool visited[v];
  57.  
  58.  
  59. 		for(int i=0;i<v;i++)
  60. 		{
  61. 			memset(visited,false,sizeof(visited[0])*v);
  62. 			for(int j=0;j<v;j++)
  63. 			cout<<visited[j];
  64. 			cout<<endl;
  65. 			bfsEachUtil(i,visited,&q[i]);
  66.  
  67. 		}
  68. 		for(int i=0;i<v;i++)
  69. 		{
  70. 			while(q[i].size())
  71. 			{
  72. 				cout<<q[i].front()<<"->";
  73. 				q[i].pop();
  74. 			}
  75. 			cout<<endl;
  76. 		}
  77. 	}
  78. 	void bfsEachUtil(int start,bool visited[],queue<int>* q)
  79. 	{
  80. 		(*q).push(start);
  81. 		visited[start]=true;
  82. 		list<int>::iterator it;
  83. 		for(it=adj[start].begin();it!=adj[start].end();++it)
  84. 		{
  85. 			if(!visited[*it])
  86. 			{
  87. 				bfsEachUtil(*it,visited,q);
  88. 			}
  89. 		}
  90. 	}
  91. };
  92. int main() {
  93. 	// your code goes here
  94. 	int v;
  95. 	cin>>v;
  96. 	graph g(v);
  97. 	int n;
  98. 	cin>>n;
  99. 	for(int i=0;i<n;i++)
  100. 	{
  101. 		int a,b;
  102. 		cin>>a>>b;
  103. 		g.add_edge(a,b);
  104. 	}
  105. 	bool visited[v];
  106. 	memset(visited,false,sizeof(visited[0])*v);
  107. 	//g.bfs(2,visited);
  108. 	g.bfsEachVertex();
  109. 	return 0;
  110. }
Success #stdin #stdout 0s 3468KB
comments (?)
stdin
copy 
4
6
0 1
0 2
1 2
2 0
2 3
3 3
stdout
copy 
0000
0000
0000
0000
0->1->2->3->
1->2->0->3->
2->0->1->3->
3->
https://ideone.com/kmR7g5
language:
C++ (gcc 8.3)
created:
8 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!