Advertisement
Norvager

Untitled

Mar 6th, 2018
182
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.09 KB | None | 0 0
  1. #define _CRT_SECURE_NO_WARNINGS
  2. #include <cstdio>
  3. #include <iostream>
  4. #include <cmath>
  5. #include <vector>
  6. #include <queue>
  7. #include <algorithm>
  8.  
  9. using namespace std;
  10.  
  11. bool dfs(vector<vector<int>>& lin, vector<int>& answer, vector<bool>& use, int& c, int& n)
  12. {
  13. if (use[c] && answer[c] == 0)
  14. return false;
  15. use[c] = true;
  16. bool sortable = true;
  17. for (int i = 1; i < lin[c].size(); i++)
  18. {
  19. //if (use[i] && answer[i] == 0)
  20. //return false;
  21. if (!use[i])
  22. sortable = sortable && dfs(lin, answer, use, lin[c][i], n);
  23. }
  24. answer[n] = c;
  25. n -= 1;
  26. return sortable;
  27. }
  28.  
  29. int main()
  30. {
  31. int n, m, a, b, d;
  32. scanf("%d %d", &n, &m);
  33. d = n;
  34. vector<vector<int>> line(n + 1, vector<int>(1));
  35. for (int i = 1; i < m; i++)
  36. {
  37. scanf("%d %d", &a, &b);
  38. line[a].push_back(b);
  39. }
  40. vector<int> ans(n + 1, 0);
  41. vector<bool> used(n + 1, false);
  42. for (int i = 1; i <= d; i++)
  43. if (!used[i])
  44. if (!dfs(line, ans, used, i, n))
  45. {
  46. printf("No");
  47. return 0;
  48. }
  49.  
  50. printf("Yes\n");
  51. for (int i = 1; i <= d; i++)
  52. printf("%d ", ans[i]);
  53.  
  54. system("pause");
  55. return 0;
  56. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement