Cod sursa(job #3340104)

Utilizator MarcheloCibotariu Mario Marchelo Data 12 februarie 2026 09:53:02
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.32 kb
#include <fstream>
#include <vector>
#define NMAX 100002
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");

int n,nrct,nr,poz;
vector<int> g[NMAX];
vector<int> gt[NMAX];
vector<int> ctc[NMAX];

bool viz[NMAX];
int  postordine[NMAX];
void citire();
void dfs(int x);
void dfst(int x);
void afisare();
int main()
{ int i;
  citire();
    for(i=1;i<=n;i++)
      if(viz[i]==0)
        dfs(i);
    for(i=n;i>=1;i--)
      if(viz[postordine[i]]==1)
      {
        nrct++;
        dfst(postordine[i]);
      }
      afisare();
    return 0;
}
void citire()
{ int i,m,x,y;
  fin>>n>>m;
  for(i=0;i<m;i++)
  {
    fin>>x>>y;
    //y intra in lita de adiacenta a lui x in g
    g[x].push_back(y);
    //x intra in lista de adiacenta a lui y in gt
    gt[y].push_back(x);
  }
}
void dfs(int x)
{ int i;
  viz[x]=1;
  //[arcurg lista de adiacenta a lui x
  for(i=0;i<g[x].size();i++)
        if(viz[g[x][i]]==0)
            dfs(g[x][i]);
  postordine[++poz]=x;
}
void dfst(int x)
{ int i;
  viz[x]=0;
  ctc[nrct].push_back(x);
  for(i=0;i<gt[x].size();i++)
    if(viz[gt[x][i]]==1)
        dfst(gt[x][i]);
}
void afisare()
{ int i,j;
  fout<<nrct<<'\n';
  for(i=1;i<=nrct;i++)
    {for(j=0;j<ctc[i].size();j++)
        fout<<ctc[i][j]<<' ';
      fout<<'\n';
    }
}