Cod sursa(job #2116849)

Utilizator Stefan_RaduStefan Radu Stefan_Radu Data 28 ianuarie 2018 10:09:11
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.46 kb
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

ifstream cin ("ctc.in");
ofstream cout ("ctc.out");

void Dfs1 (int cur_node, vector < vector < int > > &gr,
    vector < bool > &used, stack < int > &stk) {

  used[cur_node] = true;
  for (int x : gr[cur_node]) {
    if (used[x]) {
      continue;
    }

    Dfs1 (x, gr, used, stk);
  }

  stk.push (cur_node);
}

void Dfs2 (int cur_node, vector < vector < int > > &gr, 
    vector < bool > &used, vector < vector < int > > &sol, int &cnt) {

  used[cur_node] = true;
  sol[cnt].push_back (cur_node);
  for (int x : gr[cur_node]) {
    if (used[x]) {
      continue;
    }
    
    Dfs2 (x, gr, used, sol, cnt);
  }
}

int main () {

  int n, m;
  cin >> n >> m;

  vector < vector < int > > gr (n + 1), rev (n + 1);

  for (int i = 1; i <= m; ++ i) {
    int x, y;
    cin >> x >> y;

    gr[x].push_back (y);
    rev[y].push_back (x);
  }

  vector < bool > used (n + 1);
  stack < int > stk;

  for (int i = 1; i <= n; ++ i) {
    if (used[i]) {
      continue;
    }

    Dfs1 (i, gr, used, stk);
  }

  for (auto &&x : used) {
    x = false;
  }
  
  int cnt = 0;
  vector < vector < int > > sol (n + 1);
 
  while (not stk.empty ()) {

    int cur = stk.top ();
    stk.pop ();
    
    if (not used[cur]) {
      ++ cnt;
      Dfs2 (cur, rev, used, sol, cnt);
    }
  }

  cout << cnt << '\n';
  for (int i = 1; i <= cnt; ++ i) {
    for (int x : sol[i]) {
      cout << x << ' ';
    }
    cout << '\n';
  }
}