Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <string>
- #include <vector>
- #include <algorithm>
- #include <map>
- #include <queue>
- #include <deque>
- #include <set>
- using namespace std;
- void NO() {
- cout << "NO";
- exit(0);
- }
- struct Node
- {
- char color = 'w';
- bool use = false;
- set<int> dec;
- set<int> anc;
- vector<int> edges;
- };
- vector<Node> g;
- int useCnt;
- set<int> DFS(int u)
- {
- g[u].color = 'g';
- set<int> res;
- for (int v : g[u].edges)
- {
- if (g[v].color != 'w') NO();
- auto cur = DFS(v);
- for (auto i : cur) res.insert(i);
- res.insert(v);
- }
- g[u].color = 'b';
- if (g[u].dec != res) NO();
- return res;
- }
- int main()
- {
- //freopen("input.txt", "r", stdin);
- map <int, set<int>> lvls;
- int n;
- cin >> n;
- g.resize(n);
- int root = -1;
- for (int u = 0; u < n; ++u) {
- int len;
- cin >> len;
- while (len--) {
- int v;
- cin >> v;
- --v;
- g[u].dec.insert(v);
- g[v].anc.insert(u);
- }
- if (g[u].dec.size() == n - 1)
- {
- if (root != -1) NO();
- root = u;
- }
- }
- if (root == -1) NO();
- lvls[0].insert(root);
- g[root].use = ++useCnt;
- int lvl = 0;
- for (int i = 0; i < n; ++i)
- g[i].anc.erase(root);
- map <int, int> last;
- for (auto i : g[root].dec) {
- last[i] = root;
- }
- vector <pair<int, int>> sol;
- while (useCnt < n) {
- lvl++;
- for (int u = 0; u < n; ++u) {
- if (!g[u].use && g[u].anc.empty()) {
- auto it = last.find(u);
- if (it==last.end()) NO();
- else {
- sol.emplace_back(it->second, u);
- g[it->second].edges.push_back(u);
- }
- lvls[lvl].insert(u);
- g[u].use = ++useCnt;
- }
- }
- if (lvls[lvl].empty()) NO();
- last.clear();
- int sumsize = 0;
- for (auto u : lvls[lvl]) {
- for (int j = 0; j < n; ++j) {
- g[j].anc.erase(u);
- }
- for (auto j : g[u].dec) {
- if (g[j].use) NO();
- last[j] = u;
- sumsize++;
- }
- }
- if (!(last.size() == sumsize && n - useCnt == last.size())) NO();
- }
- if (DFS(root).size() != n - 1) NO();
- for (auto u : g) if (u.color != 'b') NO();
- cout << "YES" << endl;
- for (auto i : sol) {
- cout << i.first+1 << ' ' << i.second+1 << endl;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement