Cod sursa(job #3200655)

Utilizator alex210046Bratu Alexandru alex210046 Data 5 februarie 2024 16:12:40
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.11 kb
#include <fstream>
#include <vector>
using namespace std;
const int NMAX = 100001;
int N, M, nrc;
vector<int> G[NMAX], GT[NMAX], CTC[NMAX], post;
bool viz[NMAX];
ifstream f("ctc.in");
ofstream g("ctc.out");

void citire() {
   int x, y;
   f >> N >> M;
   while (M--) {
      f >> x >> y;
      G[x].push_back(y);
      GT[y].push_back(x);
   }
}

void afisare() {
   g << nrc << '\n';
   for(int i = 1; i <= nrc; i++) {
      for(const int &x : CTC[i])
         g << x << ' ';
      g << '\n';
   }
}

void dfs(int vf) {
   viz[vf] = 1;
   for(int x : G[vf])
      if(viz[x] == 0)
         dfs(x);
   post.push_back(vf);
}

void dfsGt(int vf) {
   viz[vf] = 0;
   CTC[nrc].push_back(vf);
   for(int x : GT[vf])
      if(viz[x] == 1)
         dfsGt(x);
}

void componente() {
   int i;
   for(i = 1; i <= N; i++)
      if(viz[i] == 0)
         dfs(i);
   for(i = post.size() - 1; i >= 0; i--)
      if(viz[post[i]] == 1) {
         nrc++;
         dfsGt(post[i]);
      }
}

int main() {
   citire();
   componente();
   afisare();
   f.close();
   g.close();
   return 0;
}