fork(2) download
copy 
  1. #include<stdlib.h>
  2. #include<stdio.h>
  3. #include<list>
  4. #include<iostream>
  5. using namespace std;
  6. struct graph{
  7. 	int V;
  8. 	list<int> *adj;
  9. };
  10. struct graph* create(int v){
  11. 	struct graph* g= (struct graph* )malloc(sizeof(struct graph));
  12. 	g->V=v;
  13. 	g->adj=new list<int>[v];
  14. 	return g;
  15.  
  16. }
  17. void addEdge(struct graph* g,int w,int e){
  18. 	g->adj[w].push_back(e);
  19.  
  20. }
  21. bool dfs_visit(struct graph* g,int j,char* color){
  22.  
  23. 	color[j]='g';
  24. 	//printf("%d ",j);
  25. 	list<int>::iterator k;
  26. 	for(k=g->adj[j].begin();k!=g->adj[j].end();k++){
  27.  
  28. 		if(color[*k]=='g')
  29. 		return true;
  30. 		if(color[*k]=='w'){
  31.  
  32. 			return dfs_visit(g,*k,color);
  33. 		}
  34. 	}
  35. //	printf("hello\n");
  36. 	color[j]='b';
  37. 	return false;
  38. }
  39. bool dfs(struct graph* g){
  40. 	char color[g->V];
  41. 	for(int i=0;i<g->V;i++)
  42. 	color[i]='w';
  43. 	color[0]='g';
  44. 	list<int>::iterator j;
  45. 	for(int i=0;i<g->V;i++){
  46. 		for(j=g->adj[i].begin();j!=g->adj[i].end();j++){
  47.  
  48. 			if(color[*j]=='w'){
  49.  
  50. 				bool l=dfs_visit(g,*j,color);
  51. 				if(l)
  52. 				return true;
  53.  
  54. 			}
  55. 		}
  56.  
  57. 	}
  58. 	return false;
  59.  
  60. }
  61. int main(){
  62. 	struct graph* g=create(5);
  63.  
  64. 	 addEdge(g,0, 1);
  65.     addEdge(g,0, 2);
  66.     addEdge(g,1, 2);
  67.     addEdge(g,2,3);
  68.     addEdge(g,3,0);
  69.    // addEdge(g,2, 0);
  70.     //addEdge(g,2, 3);
  71.    // addEdge(g,3, 3);
  72.     if(dfs(g))
  73.     printf("tree is cyclic\n");
  74.     else
  75.     printf("tree is not cyclic\n");
  76.  
  77. }
Success #stdin #stdout 0s 2816KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
tree is cyclic
https://ideone.com/yIq05n
language:
C++ 4.3.2 (gcc-4.3.2)
created:
9 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!