Cod sursa(job #2842703)

Utilizator popasebastian1213@gmail.comPopa Sebastian [email protected] Data 1 februarie 2022 13:21:46
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.25 kb
#include <fstream>
#include <vector>
#define NMAX 100001
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
vector <int> G[NMAX];
vector <int> GT[NMAX];
int n,post[NMAX];
bool viz[NMAX];
int nr,poz,i;
vector <int> ctc[NMAX];
void citire();
void afisare();
void dfs(int x);
void dfs1(int x);
int main()
{
    citire();
    for(i=1;i<=n;i++)
    {
     if(!viz[i])
     {
         dfs(i);
     }
    }
    for(i=n;i>=1;i--)
    {
     if(viz[post[i]]==1)
     {
         nr++;
         dfs1(post[i]);
     }
    }
    afisare();
    return 0;
}
void citire()
{
 int m,i,x,y;
 fin>>n>>m;
 for(i=1;i<=m;i++)
 {
  fin>>x>>y;
  G[x].push_back(y);
  GT[y].push_back(x);
 }

}
void dfs(int x)
{
  viz[x]=1;
  int i;
  for(i=0;i<G[x].size();i++)
  {
     if(!viz[G[x][i]])
     {
         dfs(G[x][i]);
     }
  }
  post[++poz]=x;
}
void dfs1(int x)
{
    viz[x]=0;
    int i;
    ctc[nr].push_back(x);
   for(i=0;i<GT[x].size();i++)
  {
     if(viz[GT[x][i]])
     {
         dfs1(GT[x][i]);
     }
  }

}
void afisare()
{
    fout<<nr<<'\n';
    int i,j;
   for(j=1;j<=nr;j++)
    {
     for(i=0;i<ctc[j].size();i++)
    {
     fout<<ctc[j][i]<<" ";
    }
    fout<<'\n';
    }
}