Cod sursa(job #2863403)

Utilizator vladp1324Vlad Pasare vladp1324 Data 6 martie 2022 17:45:47
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.12 kb
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

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

int n, m, nrctc, ver[100001];
vector < int > g[100001], gt[100001], v[100001];
stack < int > st;

void dfsp (int nc) {
  ver[nc] = 1;
  for (int i = 0; i < g[nc].size (); i++) {
    int nv = g[nc][i];
    if (not ver[nv])
      dfsp (nv);
  }
  st.push (nc);
}

void dfsm (int nc) {
  ver[nc] = 2;
  v[nrctc].push_back (nc);
  for (int i = 0; i < gt[nc].size (); i++) {
    int nv = gt[nc][i];
    if (ver[nv] == 1)
      dfsm (nv);
  }
}

int main()
{
  fin >> n >> m;
  for (int i = 1; i <= m; i++) {
    int x, y;
    fin >> x >> y;
    g[x].push_back (y);
    gt[y].push_back (x);
  }
  for (int i = 1; i <= n; i++)
    if (not ver[i])
      dfsp (i);
  while (not st.empty ()) {
    int nc = st.top ();
    if (ver[nc] == 1) {
      nrctc++;
      dfsm (nc);
    }
    st.pop ();
  }
  fout << nrctc << '\n';
  for (int i = 1; i <= nrctc; i++) {
    for (int j = 0; j < v[i].size (); j++)
      fout << v[i][j] << ' ';
    fout << '\n';
  }
  return 0;
}