Cod sursa(job #3340116)

Utilizator DoltuVladDoltu Vlad DoltuVlad Data 12 februarie 2026 09:56:41
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.49 kb
#include <fstream>
#include <vector>
#define NMAX 100005

using namespace std;
ifstream cin ("ctc.in");
ofstream cout ("ctc.out");

int n,nrct,poz;
vector<int>g[NMAX];
vector<int>gt[NMAX];
vector<int>ctc[NMAX];
bool viz[NMAX];
int postordine[NMAX];
int m,x,y;
void citire();
void afisare();
void dfs(int x);
void dfsgt(int x);

int main()
{
    citire();
    for (int i=1; i<=n; i++)
        if (viz[i]==0)
            dfs(i);
    for (int i=n; i>=1; i--)
        if (viz[postordine[i]]==1)
        {
            nrct++;
            dfsgt(postordine[i]);
        }
    afisare();
    return 0;
}
void citire()
{
    cin>>n>>m;
    for (int i=0; i<m; i++)
    {
        cin>>x>>y;
        ///y intra in lista 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)
{viz[x]=1;
    ///parcurg lista de adiacenta a lui x
    for (int i=0; i<g[x].size(); i++)
    {
        if (viz[g[x][i]]==0)
        {

            dfs(g[x][i]);
        }
    }
    postordine[++poz]=x;
}
void dfsgt(int x)
{viz[x]=0;
    ctc[nrct].push_back(x);
    for (int i=0; i<gt[x].size(); i++)
    {
        if (viz[gt[x][i]]==1)
        {

            dfsgt(gt[x][i]);
        }
    }
}
void afisare()
{
    cout<<nrct<<endl;
    for (int i=1;i<=nrct;i++)
    {
        for (int j=0;j<ctc[i].size();j++)
            cout<<ctc[i][j]<<' ';
        cout<<endl;
    }
}