Cod sursa(job #3340102)

Utilizator Serban_Liviu67Serban Liviu Serban_Liviu67 Data 12 februarie 2026 09:52:44
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.32 kb
#include <iostream>
#include <fstream>
#include <vector>
#define NMAX 100002
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");

int n,nrct,poz;
vector<int> G[NMAX];
vector<int> GT[NMAX];
vector<int> CTC[NMAX];

bool viz[NMAX],p;
int postordine[NMAX];

void citire()
{   int n,m,x,y,i;
    fin>>n>>m;
    for (i=0; i<m; i++)
    {
        fin>>y;
        ///ele intra in lista de a diacmta a tutora
        G[x].push_back(y);
        GT[y].push_back(x);
    }
}


void dfs(int x)
{
    int i;
    ///parcueg lista adiaceta x
    viz[x]=1;
    for (i=0; i<G[x].size(); i++)
    if (viz[G[x][i]]==0)
    dfs(G[x][i]);

    poz++;
    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';
    }
}

int main()
{
    int i;
    citire();
    for (i=1; i<=n; i++)
    {
        if (viz[i]==0)
            dfs(i);
    }

    for (i=n; i>0; i--)
        if (viz[postordine[i]]==1)
    {
        nrct++;
        dfst(postordine[i]);
    }

    afisare();
    return 0;
}