Advertisement
Guest User

Untitled

a guest
Dec 5th, 2019
129
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.15 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <set>
  4. using namespace std;
  5.  
  6. bool tf = false;
  7. int n, m;
  8. vector <set <int>> arr;
  9. bool vis[101][101];
  10. vector <int> answer;
  11.  
  12. void dfs(int i, int u) {
  13. vis[i][u] = true;
  14. for (auto v : arr[u]) {
  15. if (vis[i][v] == false) dfs(i, v);
  16. }
  17. }
  18.  
  19. int main() {
  20. cin >> n >> m;
  21. arr.resize(n + 1);
  22. for (int i = 0; i < m; i++) {
  23. int a, b;
  24. cin >> a >> b;
  25. arr[a].insert(b);
  26. }
  27. for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) vis[i][j] = false;
  28. for (int i = 1; i <= n; i++) dfs(i, i);
  29. for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) if (vis[i][j] && vis[j][i] && i != j) tf = true;
  30. if (tf) cout << "No";
  31. else {
  32. cout << "Yes" << endl;
  33. int k = 0;
  34. vector <bool> written;
  35. written.resize(n + 1);
  36. for (int i = 1; i <= n; i++) written[i] = false;
  37. while (k < n) {
  38. for (int i = 1; i <= n; i++) if (!written[i] && arr[i].size() == 0) {
  39. answer.push_back(i);
  40. written[i] = true;
  41. for (int j = 1; j <= n; j++) if (arr[j].find(i) != arr[j].end()) arr[j].erase(i);
  42. k++;
  43. }
  44. }
  45. for (int i = n - 1; i > -1; i--) cout << answer[i] << " ";
  46. }
  47. return 0;
  48. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement