Cod sursa(job #3374719)

Utilizator Iulian.CorobanCoroban Silviu Iulian Iulian.Coroban Data 9 noiembrie 2026 09:40:54
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.63 kb
#include <fstream>
#include <vector>

using namespace std;

ifstream fin("ctc.in");
ofstream fout("ctc.out");

int N, M;
vector<int> graf[100005];
vector<int> grafTranspus[100005];
bool vizitat[100005];
vector<int> ordine;
vector<vector<int>> componente;
vector<int> componentaCurenta;

void citire()
{
    fin >> N >> M;
    
    for(int i = 1; i <= M; i++)
    {
        int u, v;
        fin >> u >> v;
        
        graf[u].push_back(v);
        grafTranspus[v].push_back(u);
    }
}

void dfs1(int nod)
{
    vizitat[nod] = true;
    
    for(int vecin : graf[nod])
    {
        if(vizitat[vecin] == false)
        {
            dfs1(vecin);
        }
    }
    
    ordine.push_back(nod);
}

void dfs2(int nod)
{
    vizitat[nod] = true;
    componentaCurenta.push_back(nod);
    
    for(int vecin : grafTranspus[nod])
    {
        if(vizitat[vecin] == false)
        {
            dfs2(vecin);
        }
    }
}

int main()
{
    citire();
    
    for(int i = 1; i <= N; i++)
    {
        if(vizitat[i] == false)
        {
            dfs1(i);
        }
    }
    
    for(int i = 1; i <= N; i++)
    {
        vizitat[i] = false;
    }
    
    for(int i = N - 1; i >= 0; i--)
    {
        int nod = ordine[i];
        
        if(vizitat[nod] == false)
        {
            componentaCurenta.clear();
            
            dfs2(nod);
            
            componente.push_back(componentaCurenta);
        }
    }
    
    fout << componente.size() << "\n";
    
    for(vector<int> comp : componente)
    {
        for(int nod : comp)
        {
            fout << nod << " ";
        }
        
        fout << "\n";
    }
    
    return 0;
}