Advertisement
Guest User

Untitled

a guest
Mar 20th, 2018
77
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.38 KB | None | 0 0
  1. #include <iostream>
  2. #include <stdlib.h>
  3. #include <vector>
  4.  
  5. using namespace std;
  6.  
  7. vector<int> v[10001];
  8. int Proc[1001];
  9. bool Passed[1001];
  10. bool Conf[1001];
  11. int Levels[1001];
  12. int maxLvl = -1;
  13.  
  14. void Process (int node, int level) {
  15. if (Passed[node] == false) {
  16.  
  17. if (level >= Levels[node]) {
  18. Conf[node] = true;
  19. Passed[node] = true;
  20. Levels[node] = level;
  21. if (level > maxLvl)
  22. maxLvl = level;
  23.  
  24. int len = v[node].size();
  25. for (int i = 0; i < len; i++)
  26. Process(v[node][i], level + 1);
  27.  
  28. Passed[node] = false;
  29. }
  30. } else {
  31. cout << "-1";
  32. exit(0);
  33. }
  34. }
  35.  
  36. int main () {
  37. int nodes, conn;
  38. cin >> nodes >> conn;
  39.  
  40. for (int i = 0; i < conn; i++) {
  41. int a, b;
  42. cin >> a >> b;
  43. v[a].push_back(b);
  44. }
  45.  
  46. for (int i = 1; i <= nodes; i++) {
  47. if (!Conf[i])
  48. Process(i, 0);
  49. }
  50.  
  51. for (int i = 1; i <= nodes; i++)
  52. v[i].clear();
  53.  
  54. for (int i = 1; i <= nodes; i++) {
  55. v[Levels[i]].push_back(i);
  56. }
  57.  
  58. int index = 1;
  59.  
  60. for (int i = 0; i <= maxLvl; i++) {
  61. int len = v[i].size();
  62. for (int k = 0; k < len; k++) {
  63. Proc[v[i][k]] = index++;
  64. }
  65. }
  66.  
  67. for (int i = 1; i <= nodes; i++) {
  68. cout << Proc[i] << " ";
  69. }
  70. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement