fork download
copy 
  1. #include <stdio.h>
  2. #include <string.h>
  3. #include <stdlib.h>
  4. #include <math.h>
  5. #include <ctype.h>
  6. #define R(t) scanf("%d",&t)
  7. #define W(t) printf("%d ",t)
  8. #define rep(i,x,y) for(i=x;i<y;i++)
  9.  
  10. typedef struct adjnode
  11. {
  12. 	int x;
  13. 	struct adjnode *next;
  14. }node;
  15.  
  16. typedef struct adjlist
  17. {
  18. 	node *head;
  19. }list;
  20.  
  21. typedef struct graph
  22. {
  23. 	int V;
  24. 	list *neighbors;
  25. }graph;
  26.  
  27. typedef struct stack
  28. {
  29. 	int x;
  30. 	struct stack *next;
  31. }stack;
  32.  
  33. stack *top;
  34.  
  35. stack* push(int x)
  36. {
  37. 	if(!top)
  38. 	{
  39. 		top=(stack*)malloc(sizeof(stack));
  40. 		top->next=NULL;
  41. 		top->x=x;
  42. 	}
  43. 	else
  44. 	{
  45. 		stack *temp=(stack*)malloc(sizeof(stack));
  46. 		temp->next=top;
  47. 		temp->x=x;
  48. 		top=temp;
  49. 	}
  50. 	return top;
  51. }
  52.  
  53. int stktop()
  54. {
  55. 	return top->x;
  56. }
  57.  
  58. int isEmpty()
  59. {
  60. 	return !top?1:0;
  61. }
  62.  
  63. int pop()
  64. {
  65. 	if(top->next!=NULL)
  66. 	{
  67. 		int y=top->x;
  68. 		stack* temp=top;
  69. 		top=top->next;
  70. 		//free(temp);
  71. 		return y;
  72. 	}
  73. 	else
  74. 	{
  75. 		int y=top->x;
  76. 		//free(top);
  77. 		return y;
  78. 	}
  79. }
  80.  
  81. int *visited,*arrival,*departure;
  82.  
  83. graph* CreateGraph(int V)
  84. {
  85. 	graph *g=(graph*)malloc(sizeof(graph));
  86. 	g->V=V;
  87. 	g->neighbors=(list*)malloc(sizeof(list)*V);
  88. 	int i;
  89. 	rep(i,0,V)
  90. 		g->neighbors[i].head=NULL;
  91. 	return g;
  92. }
  93.  
  94. node* New_Node(int val)
  95. {
  96. 	node* temp=(node*)malloc(sizeof(node));
  97. 	temp->next=NULL;
  98. 	temp->x=val;
  99. 	return temp;
  100. }
  101.  
  102. void AddEdge(graph *g,int i,int j)
  103. {
  104. 	node* t1=New_Node(i);
  105. 	t1->next=g->neighbors[j].head;
  106. 	g->neighbors[j].head=t1;
  107.  
  108. 	node* t2=New_Node(j);
  109. 	t2->next=g->neighbors[i].head;
  110. 	g->neighbors[i].head=t2;
  111. }
  112.  
  113. int t=0;
  114.  
  115. void DFS(graph* g,int v)
  116. {
  117. 	push(v);
  118. 	while(!isEmpty())
  119. 	{
  120. 		int x=stktop();
  121. 		arrival[x]=t++;
  122. 		pop();
  123. 		if(!visited[x])
  124. 		{
  125. 			visited[x]=1;
  126. 			node *temp=g->neighbors[x].head;
  127. 			while(temp)
  128. 			{
  129. 				if(!visited[temp->x])
  130. 					push(temp->x);
  131. 				temp=temp->next;
  132. 			}
  133. 		}
  134. 		departure[x]=t++;
  135. 	}
  136. }
  137.  
  138. int TreeEdge(int a,int b)
  139. {
  140. 	if(arrival[a]<arrival[b] && arrival[b]<departure[b] && departure[b]<departure[a]) return 1;
  141. 	else return 0;
  142. }
  143.  
  144. int BackEdge(int a,int b)
  145. {
  146. 	if(arrival[b]<=arrival[a] && arrival[a]<departure[a] && departure[a]<=departure[b]) return 1;
  147. 	else return 0;
  148. }
  149.  
  150. int main()
  151. {
  152. 	graph *g =CreateGraph(10);
  153. 	departure=(int*)calloc(10,sizeof(int));
  154. 	arrival=(int*)calloc(10,sizeof(int));
  155. 	visited=(int*)calloc(10,sizeof(int));
  156. 	AddEdge(g,0,2);
  157. 	AddEdge(g,0,1);
  158. 	AddEdge(g,1,4);
  159. 	AddEdge(g,3,4);
  160. 	AddEdge(g,3,5);
  161. 	AddEdge(g,4,5);
  162. 	AddEdge(g,5,6);
  163. 	AddEdge(g,6,7);
  164. 	AddEdge(g,6,8);
  165. 	DFS(g,0);
  166. 	int i;
  167. 	for(i=0;i<g->V;i++)
  168. 	{
  169. 		printf("%d :[%d,%d]\n",i,arrival[i],departure[i]);
  170. 	}
  171. 	return 0;
  172. }
Time limit exceeded #stdin #stdout 5s 2180KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/FywSHo
language:
C (gcc 8.3)
created:
9 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!