Advertisement
overwater

Untitled

May 29th, 2015
236
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.80 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4.  
  5. void dfs1(int v, vector <bool> &isUsed, vector <vector <int> > &edges, vector <int> &order) {
  6.     isUsed[v] = true;
  7.     for (int i = 0; i < edges[v].size(); ++i) {
  8.         if (!isUsed[edges[v][i]])
  9.             dfs1(edges[v][i], isUsed, edges, order);
  10.     }
  11.     order.push_back(v);
  12. }
  13.  
  14. void dfs2(int v, vector <bool> &isUsed, vector <vector <int> > &edges_reverse, vector <int> &component, int c) {
  15.     isUsed[v] = true;
  16.     component[v] = c;
  17.     for (int i = 0; i < edges_reverse[v].size(); ++i)
  18.         if (!isUsed[edges_reverse[v][i]])
  19.             dfs2(edges_reverse[v][i], isUsed, edges_reverse, component, c);
  20. }
  21.  
  22. int main() {
  23.     int n;
  24.     cin >> n;
  25.  
  26.     vector < vector <int> > edges(2 * n);
  27.     vector < vector <int> > edges_reverse(2 * n);
  28.     for (int i = 0; i < n; ++i) {
  29.         int k, temp;
  30.         cin >> k;
  31.         cin >> temp;
  32.         edges[i].push_back(n + temp - 1);
  33.         edges_reverse[n + temp - 1].push_back(i);
  34.         for (int j = 1; j < k; ++j) {
  35.             cin >> temp;
  36.             edges[n + temp - 1].push_back(i);
  37.             edges_reverse[i].push_back(n + temp - 1);
  38.         }
  39.     }
  40.  
  41.     vector <int> comp(2 * n);
  42.     n *= 2;
  43.    
  44.     vector <int> order;
  45.     vector <bool> isUsed(n, false);
  46.     for (int i = 0; i < n; ++i)
  47.         if (!isUsed[i])
  48.             dfs1(i, isUsed, edges, order);
  49.     isUsed.assign(n, false);
  50.     int c = 1;
  51.     for (int i = 0; i < n; ++i) {
  52.         int v = order[n - 1 - i];
  53.         if (!isUsed[v]) {
  54.             dfs2(v, isUsed, edges_reverse, comp, c);
  55.             c++;
  56.         }
  57.     }
  58.  
  59.     n /= 2;
  60.     vector < vector <int> > answers(n);
  61.     for (int i = 0; i < n; ++i)
  62.         for (int j = 0; j < edges[i + n].size(); ++j)
  63.             if (comp[i + n] == comp[edges[i + n][j]])
  64.                 answers[edges[i + n][j]].push_back(i);
  65.  
  66.     for (int i = 0; i < n; ++i) {
  67.         cout << answers[i].size();
  68.         for (int j = 0; j < answers[i].size(); ++j)
  69.             cout << ' ' << answers[i][j] + 1;
  70.         cout << endl;
  71.     }
  72.  
  73.     return 0;
  74. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement