fork download 
  1. /*Shovkoplyas Grigory in the house*/
  2. #include<cstdio>
  3. #include<iostream>
  4. #include<algorithm>
  5. #include<ctime>
  6. #include<deque>
  7. #include<cassert>
  8. #include<cmath>
  9. #include<cstdlib>
  10. #include<cstring>
  11. #include<string>
  12. #include<vector>
  13. #include<set>
  14. #include<map>
  15. using namespace std;
  16.  
  17. #define name "gods"
  18.  
  19. int n;
  20. vector<vector<int> > g;
  21. vector<int> was;
  22. vector<int> color;
  23. bool bad;
  24. deque<int> up, down;
  25. vector<int> au, ad;
  26.  
  27. void dfs(int v, int c)
  28. {
  29.   was[v] = 1;
  30.   color[v] = c;
  31.   for(int i = 0; i < (int)g[v].size(); i++)
  32.   {
  33.     int u = g[v][i];
  34.     if(color[u] == c)
  35.       bad = true;
  36.     else if(!was[u])
  37.       dfs(u, c ^ 1);
  38.  
  39.   }
  40. }
  41.  
  42. void deal(int v, int dir, int p)
  43. {
  44.   if(g[v].size() == 1)
  45.     return;
  46.   int n = g[v].size();
  47.   if(g[v][0] != p && g[v][n - 1] != p)
  48.   {
  49.     if(!color[v])
  50.     {
  51.       assert((int)down.size() == 1);
  52.       down.resize(0);
  53.       for(int i = 0; i < n; i++)
  54.       {
  55.         int u = g[v][i];
  56.         if(u != p && was[u])
  57.           bad = true;
  58.         was[u] = 1;
  59.         down.push_back(u);
  60.       }
  61.     }
  62.     else
  63.     {
  64.       assert((int)up.size() == 1);
  65.       up.resize(0);
  66.       for(int i = 0; i < n; i++)
  67.       {
  68.         int u = g[v][i];
  69.         if(u != p && was[u])
  70.           bad = true;
  71.         was[u] = 1;
  72.         up.push_back(u);
  73.       }
  74.     }
  75.     if(!bad)
  76.       deal(g[v][0], -1, v), deal(g[v][n - 1], 1, v);
  77.     return; 
  78.   }
  79.   if(g[v][0] != p)
  80.     reverse(g[v].begin(), g[v].end());
  81.   for(int i = 1; i < n; i++)
  82.   {
  83.     int u = g[v][i];
  84.     if(was[u])
  85.       bad = true;
  86.         was[u] = 1;
  87.     if(dir == 1)
  88.     {
  89.       if(color[v])
  90.         up.push_back(u);
  91.       else
  92.         down.push_back(u);
  93.     }
  94.     else
  95.     {
  96.       if(color[v])
  97.         up.push_front(u);
  98.       else
  99.         down.push_front(u);
  100.     } 
  101.   }
  102.   if(!bad)
  103.     deal(g[v][n - 1], dir, v);
  104. }
  105.  
  106. void make_graph(int v)
  107. {
  108.   was[v] = 1;
  109.   if((int)g[v].size() == 0)
  110.   {
  111.     if(!color[v])
  112.       au.push_back(v);
  113.     else
  114.       ad.push_back(v);
  115.     return;
  116.   }
  117.   if(!color[v])
  118.     up.push_back(v);
  119.   else
  120.     down.push_back(v);
  121.   for(int i = 0; i < (int)g[v].size(); i++)  
  122.   {
  123.         int u = g[v][i];
  124.     if(was[u])
  125.       bad = true;
  126.     was[u] = 1;
  127.     if(color[v])
  128.       up.push_back(u);
  129.     else
  130.       down.push_back(u);
  131.   }
  132.   deal(g[v][0], -1, v);
  133.   if((int)g[v].size() > 1)
  134.     deal(g[v][g[v].size() - 1], 1, v);
  135.   for(int i = 0; i < (int)up.size(); i++)
  136.     au.push_back(up[i]);
  137.   for(int i = 0; i < (int)down.size(); i++)
  138.     ad.push_back(down[i]);
  139.     up.resize(0);
  140.     down.resize(0);
  141. }
  142.  
  143. int main()
  144. {
  145.   freopen(name".in", "r", stdin);
  146.   freopen(name".out", "w", stdout);
  147.   cin >> n;
  148.   color.assign(n, -1);
  149.   was.assign(n, 0);
  150.   g.resize(n);
  151.   for(int i = 0; i < n; i++)
  152.   {
  153.     int k;
  154.     cin >> k;
  155.     set<int> wwas;
  156.     for(int j = 0; j < k; j++)
  157.     {
  158.       int a;
  159.       cin >> a;
  160.       a--;
  161.       if (wwas.count(a) == 0)
  162.           g[i].push_back(a);
  163.       wwas.insert(a);
  164.     }
  165.   }
  166.   for(int i = 0; i < n; i++)
  167.     if(!was[i])
  168.       dfs(i, 0);
  169.   //cerr << bad << endl;
  170.   for(int i = 0; i < n; i++)
  171.   {
  172.     if(g[i].size() < 3)
  173.       continue;
  174.     int k = 0;
  175.     for(int j = 0; j < (int)g[i].size(); j++)
  176.     {
  177.       int u = g[i][j];
  178.       if(g[u].size() > 1)
  179.         k++;
  180.     }
  181.     if(k > 2)
  182.     {
  183.       bad = true;
  184.       break;
  185.     }
  186.   }
  187.   if(bad)
  188.   {
  189.     cout << "-1";
  190.     return 0;
  191.   }
  192.   for(int i = 0; i < n; i++)
  193.   {
  194.     bool e = false;
  195.     if(g[i].size() < 3)
  196.       continue;
  197.     for(int j = 0; j < (int)g[i].size(); j++)
  198.     {
  199.       if(g[g[i][j]].size() > 1)
  200.       {
  201.         if(!e)
  202.           swap(g[i][j], g[i][0]), e = true;
  203.         else
  204.           swap(g[i][j], g[i][g[i].size() - 1]);
  205.       }
  206.     }
  207.  
  208.   }
  209.   was.assign(n, 0);
  210.   for(int i = 0; i < n; i++)
  211.     if(!was[i])
  212.       make_graph(i);
  213.   if(bad)
  214.   {
  215.     cout << "-1";
  216.     return 0;
  217.   }
  218.   cout << au.size() << ' ' << ad.size() << endl;
  219.   for(int i = 0; i < (int)au.size(); i++)
  220.     cout << au[i] + 1 << ' ';
  221.   cout << endl;
  222.   for(int i = 0; i < (int)ad.size(); i++)
  223.     cout << ad[i] + 1 << ' ';
  224.   cout << endl;
  225.   return 0;
  226. }
  227.  
  228.  
Success #stdin #stdout 0s 3488KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/B5nTdT
language:
C++ (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!