Cod sursa(job #2216114)

Utilizator dahaandreiDaha Andrei Codrin dahaandrei Data 25 iunie 2018 12:49:41
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.06 kb
#include <fstream>
#include <vector>

using namespace std;

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

const int MAXN = 1e5;
const int MAXM = 2e5;

vector<int> g1[MAXN + 1], g2[MAXN + 1];
int n, m, cnt;
vector<int> ctc[MAXN + 1], nodes;
bool viz[MAXN + 1];

void dfs1(int node) {
  viz[node] = 1;

  for (auto x : g1[node]) {
    if (!viz[x]) {
      nodes.push_back(x);
      dfs1(x);
    }
  }
}

void dfs2(int node) {
  ctc[cnt].push_back(node);
  viz[node] = 0;

  for (auto x : g2[node]) {
    if (viz[x]) {
      dfs2(x);
    }
  }

}

int main() {
  in >> n >> m;

  for (int i = 1; i <= m; ++ i) {
    int a, b;
    in >> a >> b;
    g1[a].push_back(b);
    g2[b].push_back(a);
  }

  for (int i = 1; i <= n; ++ i) {
    if (!viz[i]) {
      dfs1(i);
    }
  }

  for (auto x : nodes) {
    if (viz[x]) {
      ++ cnt;
      dfs2(x);
    }
  }

  out << cnt << '\n';

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

  return 0;
}