fork download
copy 
  1. #include <stack>
  2. #include <cstdio>
  3.  
  4. using namespace std;
  5.  
  6.  
  7. int main(int argc, char* argv[])
  8. {
  9. 	const int maxn = 100;
  10. 	stack < int > s;
  11. 	static int color[maxn];
  12. 	static bool edge[maxn][maxn];
  13. 	const int white = 0, grey = 1, black = 2;
  14.  
  15. 	int n, M;	
  16. 	scanf("%d %d", &n, &M);
  17. 	for(int i=0; i<n; i++)
  18. 		for(int j=0; j<n; j++)
  19. 			edge[i][j] = false;
  20. 	for(int k=0; k<M; k++)
  21. 	{
  22. 		int u,v;
  23. 		scanf("%d %d", &u, &v);
  24. 		edge[u-1][v-1] = true;
  25. 	}
  26. 	int start = 0;
  27. 	bool cycle_found = false;
  28. 	for(int i=0; i<n; i++)
  29. 		color[i] = white;
  30.  
  31. 	s.push(start);
  32. 	while (!s.empty()){
  33. 		int from = s.top();
  34. 		if (color[from] == white){
  35. 			color[from] = grey;
  36. 			for (int to = 0; to < n; ++to){
  37. 				if (edge[from][to])
  38. 					if(color[to] == white)
  39. 						s.push(to);
  40. 					else if(color[to] == grey)
  41. 						cycle_found = true; // при желании можно что-то как-то оборвать
  42. 			}		
  43. 		}else{ // вершина помеченна, значит мы в нее пришли уже на выходе из рекурсии из потомков
  44. 			// делаем все, что надо делать после выхода dfs из потомков вершины
  45.  
  46. 			color[from] = black;
  47. 			s.pop();
  48. 		}
  49. 	}
  50. 	printf("%s\n", cycle_found ? "cycle found" : "acycled");
  51. }
  52.  
Success #stdin #stdout 0.02s 2872KB
comments (?)
stdin
copy 
4 5
1 2
1 3
2 3
3 4
2 4
stdout
copy 
acycled
https://ideone.com/pUkoq
language:
C++ (gcc 8.3)
created:
12 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!