Cod sursa(job #2338037)

Utilizator Stefan_RaduStefan Radu Stefan_Radu Data 6 februarie 2019 22:02:31
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.78 kb
// By Stefan Radu

#include <algorithm>
#include <fstream>
#include <iomanip>
#include <cassert>
#include <vector>
#include <string>
#include <cctype>
#include <queue>
#include <deque>
#include <cmath>
#include <stack>
#include <map>
#include <set>

using namespace std;

#define sz(x) (int)(x).size()

typedef pair < int, int > pii;
typedef long long ll;
typedef long double ld;
typedef unsigned int ui;
typedef unsigned long long ull;

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

stack < int > stk;

void Dfs1(int curNode, vector < vector < int > > &gr, vector < bool > &used) {

  used[curNode] = true;
  for (auto x : gr[curNode]) {
    if (used[x]) continue;
    Dfs1(x, gr, used);
  }
  stk.push(curNode);
}

vector < int > aux;
void Dfs2(int curNode, vector < vector < int > > &gr, vector < bool > &used) {

  used[curNode] = true;
  aux.push_back(curNode);
  for (auto x : gr[curNode]) {
    if (used[x]) continue;
    Dfs2(x, gr, used);
  }
}

int main() {

/*   ios::sync_with_stdio(false); */
/*   cin.tie(0);cout.tie(0); */

/*   freopen("input", "r", stdin); */
/*   freopen("output", "w", stdout); */

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

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

  for (int i = 1; i <= m; ++ i) {

    int a, b;
    cin >> a >> b;

    gr[a].push_back (b);
    invGr[b].push_back (a);
  }

  vector < bool > used(n + 1);
  for (int i = 1; i <= n; ++ i) {
    if (used[i]) continue;
    Dfs1(i, gr, used);
  }

  fill(used.begin(), used.end(), false);
  
  vector < vector < int > > sol;
  while (not stk.empty()) {
    int cur = stk.top();
    stk.pop();

    if (used[cur]) continue;

    Dfs2(cur, invGr, used);
    sol.push_back(aux);
    aux.clear();
  }

  cout << sz(sol) << '\n';
  for (auto vect : sol) {
    for (auto x : vect) cout << x << ' ';
    cout << '\n';
  }
}