Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- using namespace std;
- void dfs1(int v, vector <bool> &isUsed, vector <vector <int> > &edges, vector <int> &order) {
- isUsed[v] = true;
- for (int i = 0; i < edges[v].size(); ++i) {
- if (!isUsed[edges[v][i]])
- dfs1(edges[v][i], isUsed, edges, order);
- }
- order.push_back(v);
- }
- void dfs2(int v, vector <bool> &isUsed, vector <vector <int> > &edges_reverse, vector <int> &component, int c) {
- isUsed[v] = true;
- component[v] = c;
- for (int i = 0; i < edges_reverse[v].size(); ++i)
- if (!isUsed[edges_reverse[v][i]])
- dfs2(edges_reverse[v][i], isUsed, edges_reverse, component, c);
- }
- int main() {
- int n;
- cin >> n;
- vector < vector <int> > edges(2 * n);
- vector < vector <int> > edges_reverse(2 * n);
- for (int i = 0; i < n; ++i) {
- int k, temp;
- cin >> k;
- cin >> temp;
- edges[i].push_back(n + temp - 1);
- edges_reverse[n + temp - 1].push_back(i);
- for (int j = 1; j < k; ++j) {
- cin >> temp;
- edges[n + temp - 1].push_back(i);
- edges_reverse[i].push_back(n + temp - 1);
- }
- }
- vector <int> comp(2 * n);
- n *= 2;
- vector <int> order;
- vector <bool> isUsed(n, false);
- for (int i = 0; i < n; ++i)
- if (!isUsed[i])
- dfs1(i, isUsed, edges, order);
- isUsed.assign(n, false);
- int c = 1;
- for (int i = 0; i < n; ++i) {
- int v = order[n - 1 - i];
- if (!isUsed[v]) {
- dfs2(v, isUsed, edges_reverse, comp, c);
- c++;
- }
- }
- n /= 2;
- vector < vector <int> > answers(n);
- for (int i = 0; i < n; ++i)
- for (int j = 0; j < edges[i + n].size(); ++j)
- if (comp[i + n] == comp[edges[i + n][j]])
- answers[edges[i + n][j]].push_back(i);
- for (int i = 0; i < n; ++i) {
- cout << answers[i].size();
- for (int j = 0; j < answers[i].size(); ++j)
- cout << ' ' << answers[i][j] + 1;
- cout << endl;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement