Advertisement
Guest User

Untitled

a guest
Jan 18th, 2020
67
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.10 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. using namespace std;
  5.  
  6. vector<int> g[100000];
  7. int used[100000];
  8. vector<int> order;
  9.  
  10. bool flag = 0;
  11.  
  12. void dfs(int v) {
  13. used[v] = 1;
  14. for (int u: g[v]) {
  15. if (!used[u])
  16. dfs(u);
  17. else if (used[u] == 1)
  18. flag = 1;
  19. }
  20. used[v] = 2;
  21. order.push_back(v);
  22. }
  23.  
  24.  
  25. int main() {
  26. int n, m;
  27. cin >> n >> m;
  28. for (int i = 0; i < m; i++) {
  29. int u, v;
  30. cin >> u >> v;
  31. u--; v--;
  32. g[u].push_back(v);
  33. }
  34. for (int i = 0; i < n; i++) {
  35. if (!used[i])
  36. dfs(i);
  37. }
  38. reverse(order.begin(), order.end());
  39. for(int i = 1; i < order.size(); i++) {
  40. for (int j = 1; j < n; j++) {
  41. if (g[order[i - 1]][j] != order[i]) {
  42. cout << "NO";
  43. exit(0);
  44. }
  45. }
  46. }
  47. if (flag)
  48. cout << "NO";
  49. else {
  50. cout << "YES" << '\n';
  51. for (int v: order) {
  52. cout << v + 1;
  53. cout << ' ';
  54. }
  55. }
  56. return 0;
  57. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement