Spoj TOPOSORT - Topological Sorting Solution

  

Solution in C++:

///**********ALLAH IS ALMIGHTY************///

///AH Tonmoy

///Department of CSE,23rd batch

///Islamic University,Bangladesh  

1. #include<bits/stdc++.h>
2. using namespace std;
3. #define mx 10009
4. #define white 0
5. #define gray 1
6. #define black 2
7. vector < int > graph[mx];
8. int color[mx];
9. bool cycle;
10. vector < int > result;
11. void dfs(int node)
12. {
13. color[node] = gray;
14. sort(graph[node].begin(), graph[node].end());
15. for (int i = graph[node].size() - 1; i >= 0; i--)
16. {
17. int next = graph[node][i];
18. if (color[next] == white)
19. {
20. dfs(next);
21. }
22. else if (color[next] == gray)
23. {
24. cycle = true;
25. return ;
26. }
27. }
28. color[node] = black;
29. result.push_back(node);
30. }
31. int main()
32. {
33. cycle = false;
34. int node,edge;
35. scanf("%d%d", &node, &edge);
36. for (int i = 1; i <= edge; i++)
37. {
38. int u,v;
39. scanf("%d%d", &u, &v);
40. graph[u].push_back(v);
41. }
42.  
43. for (int i = node; i >= 1; i--)
44. {
45. if (color[i] == white)
46. dfs(i);
47. }
48. if (cycle == true)
49. {
50. printf("Sandro fails.\n");
51. }
52. else
53. {
54. for (int i = result.size() - 1; i >= 0; i--)
55. {
56. printf("%d ", result[i]);
57. }
58. cout<<endl;
59. }
60. return 0;
61. }