Advertisement
cincout

Untitled

Jan 24th, 2020
127
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.13 KB | None | 0 0
  1. #include <iostream>
  2. #include <string>
  3. #include <vector>
  4. #include <algorithm>
  5. #include <map>
  6. #include <queue>
  7. #include <deque>
  8. #include <set>
  9.  
  10. using namespace std;
  11.  
  12. void NO() {
  13. cout << "NO";
  14. exit(0);
  15. }
  16.  
  17. struct Node
  18. {
  19. char color = 'w';
  20. bool use = false;
  21. set<int> dec;
  22. set<int> anc;
  23. vector<int> edges;
  24. };
  25. vector<Node> g;
  26.  
  27. int useCnt;
  28.  
  29. set<int> DFS(int u)
  30. {
  31. g[u].color = 'g';
  32.  
  33. set<int> res;
  34.  
  35. for (int v : g[u].edges)
  36. {
  37. if (g[v].color != 'w') NO();
  38.  
  39. auto cur = DFS(v);
  40. for (auto i : cur) res.insert(i);
  41. res.insert(v);
  42. }
  43.  
  44. g[u].color = 'b';
  45.  
  46. if (g[u].dec != res) NO();
  47. return res;
  48. }
  49.  
  50. int main()
  51. {
  52. //freopen("input.txt", "r", stdin);
  53. map <int, set<int>> lvls;
  54. int n;
  55. cin >> n;
  56. g.resize(n);
  57.  
  58. int root = -1;
  59. for (int u = 0; u < n; ++u) {
  60. int len;
  61. cin >> len;
  62. while (len--) {
  63. int v;
  64. cin >> v;
  65. --v;
  66. g[u].dec.insert(v);
  67. g[v].anc.insert(u);
  68. }
  69. if (g[u].dec.size() == n - 1)
  70. {
  71. if (root != -1) NO();
  72. root = u;
  73. }
  74. }
  75.  
  76. if (root == -1) NO();
  77.  
  78. lvls[0].insert(root);
  79. g[root].use = ++useCnt;
  80. int lvl = 0;
  81. for (int i = 0; i < n; ++i)
  82. g[i].anc.erase(root);
  83.  
  84. map <int, int> last;
  85.  
  86. for (auto i : g[root].dec) {
  87. last[i] = root;
  88. }
  89.  
  90. vector <pair<int, int>> sol;
  91.  
  92. while (useCnt < n) {
  93. lvl++;
  94. for (int u = 0; u < n; ++u) {
  95. if (!g[u].use && g[u].anc.empty()) {
  96. auto it = last.find(u);
  97. if (it==last.end()) NO();
  98. else {
  99. sol.emplace_back(it->second, u);
  100. g[it->second].edges.push_back(u);
  101. }
  102. lvls[lvl].insert(u);
  103. g[u].use = ++useCnt;
  104. }
  105. }
  106. if (lvls[lvl].empty()) NO();
  107. last.clear();
  108. int sumsize = 0;
  109. for (auto u : lvls[lvl]) {
  110. for (int j = 0; j < n; ++j) {
  111. g[j].anc.erase(u);
  112. }
  113. for (auto j : g[u].dec) {
  114. if (g[j].use) NO();
  115. last[j] = u;
  116. sumsize++;
  117. }
  118. }
  119. if (!(last.size() == sumsize && n - useCnt == last.size())) NO();
  120. }
  121.  
  122. if (DFS(root).size() != n - 1) NO();
  123. for (auto u : g) if (u.color != 'b') NO();
  124.  
  125. cout << "YES" << endl;
  126. for (auto i : sol) {
  127. cout << i.first+1 << ' ' << i.second+1 << endl;
  128. }
  129.  
  130. return 0;
  131. }
  132.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement