Cod sursa(job #3341226)

Utilizator basu_adrianBasu Adrian basu_adrian Data 18 februarie 2026 16:54:45
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.17 kb
#include <fstream>
#include <vector>
#define NMAX 100002
using namespace std;
ifstream fin ("ctc.in");
ofstream fout("ctc.out");
int n, m, nr, nrctc;
vector <int> G[NMAX];
vector <int> Gt[NMAX];
vector <int> CTC[NMAX];
int post[NMAX];
bool viz[NMAX];
void citire();
void  dfs(int x);
void dfs2(int x);
void afisare();
int main()
{int i;
 citire();

 for(i=1; i<=n; i++)
     if(!viz[i]) dfs(i);

 for(i=1; i<=n; i++) viz[i]=0;

 for(i=nr; i>0; i--)
     if(!viz[post[i]])
        {nrctc++;
         dfs2(post[i]);
        }

 afisare();
 return 0;
}

void citire()
{int 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)
{int i;
 viz[x]=1;
 for(i=0; i<G[x].size(); i++)
     if(!viz[G[x][i]])
        dfs(G[x][i]);
 post[++nr]=x;
}

void dfs2(int x)
{int i;
 viz[x]=1;
 CTC[nrctc].push_back(x);
 for(i=0; i<Gt[x].size(); i++)
     if(!viz[Gt[x][i]])
        dfs2(Gt[x][i]);

}

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