Cod sursa(job #3268174)

Utilizator divadddDavid Curca divaddd Data 13 ianuarie 2025 20:26:46
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.11 kb
#include <bits/stdc++.h>
using namespace std;
const int NMAX = 1e5+2;
int n,m,idx[NMAX],vis[NMAX];
vector<int> v[NMAX],t[NMAX],dfsOrder,comp[NMAX];

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

void dfs1(int nod){
  vis[nod] = true;
  for(int fiu: v[nod]){
    if(vis[fiu] == true){
      continue ;
    }
    dfs1(fiu);
  }
  dfsOrder.push_back(nod);
}

void dfs2(int nod, int col){
  idx[nod] = col;
  comp[col].push_back(nod);
  for(int fiu: t[nod]){
    if(idx[fiu] != 0){
      continue ;
    }
    dfs2(fiu, col);
  }
}

int main() {
  fin >> n >> m;
  for(int i = 1; i <= m; i++){
    int x, y;
    fin >> x >> y;
    v[x].push_back(y);
    t[y].push_back(x);
  }
  for(int i = 1; i <= n; i++){
    if(!vis[i]){
      dfs1(i);
    }
  }
  reverse(dfsOrder.begin(), dfsOrder.end());
  int k = 0;
  for(int it: dfsOrder){
    if(idx[it] == 0){
      dfs2(it, ++k);
    }
  }
  fout << k << "\n";
  for(int i = 1; i <= k; i++){
    sort(comp[i].begin(), comp[i].end());
    for(int it: comp[i]){
      fout << it << " ";
    }
    fout << "\n";
  }
  return 0;
}