Cod sursa(job #2849588)

Utilizator Asgari_ArminArmin Asgari Asgari_Armin Data 15 februarie 2022 13:06:38
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.18 kb
#include <fstream>
#include <vector>

using namespace std;

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

const int NMAX = 1e5;
const int MMAX = 2e5;

int viz[NMAX + 2];
int ctc[NMAX + 2];
vector <int> ans[NMAX + 2];
int currComp;
vector <int> g[NMAX + 2], ginv[NMAX + 2];
vector <int> order;

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

  for (int next : g[node]) 
    if (!viz[next]) {
      dfs_topological(next);
      order.push_back(next);
    }
}

void dfs_ctc (int node) {
  viz[node] = 1;
  ctc[node] = currComp;
  ans[currComp].push_back(node);

  for (int next : ginv[node]) 
    if (!viz[next]) {
      dfs_ctc(next);
    }
}

int main() {
  int n, m, i, x, y;

  fin >> n >> m;
  
  for (i = 1; i <= m; ++i) {
    fin >> x >> y;

    g[x].push_back(y);
    ginv[y].push_back(x);
  }
  
  for (i = 1; i <= n; ++i) 
    if (!viz[i]) 
      dfs_topological(i);
  
  for (i = 1; i <= n; ++i) viz[i] = 0;

  currComp = 1;
  for (i = order.size() - 1; i >= 0; --i) 
    if (!viz[order[i]]) {
      dfs_ctc(order[i]);
      ++currComp;
    }
  
  fout << currComp - 1 << "\n";

  for (i = 1; i <= currComp; ++i, fout << "\n") 
    for (int x : ans[i])
      fout << x << " "; 
  return 0;
}