Cod sursa(job #3371879)

Utilizator mitoceanuci@gmail.comMitoceanu Ciprian [email protected] Data 1 noiembrie 2026 15:01:02
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.58 kb
#include <vector>
#include <fstream>
#include <list>
#include <stack>
#include <stdbool.h>

int const N = 100005;

std::vector<int> graf[N];
std::vector<int> grafT[N];
std::vector<int> componenteConexe[N];
std::vector<bool> vizitat(N,false);
std::vector<bool> assigned(N,false);
std::vector<int> lista;
int numarComponente = 0;

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

void Visit(int nod)
{
    if(vizitat[nod] == false){
        vizitat[nod] = true;
        
        for(auto vecin : graf[nod])
        {
            Visit(vecin);
        }

        lista.push_back(nod);
    }
}

void Assign(int nod, int root)
{
    if(assigned[nod] == false)
    {
        assigned[nod] = true;
        componenteConexe[root].push_back(nod);
        for(auto vecin : grafT[nod])
        {
            Assign(vecin, root);
        }
    }
}

int main()
{
    int n,m;
    fin>>n>>m;
    

    for(int i{0}; i<m;i++)
    {
        int x, y;
        fin>>x>>y;
        graf[x].push_back(y);
        grafT[y].push_back(x);
    }

    for(auto i{1}; i <= n; i++)
    {
        Visit(i);
    }
    
    for(int i = lista.size() - 1; i >= 0; --i)
    {
        int nod = lista[i];
        if(!assigned[nod])
        {
            numarComponente ++;
            Assign(nod, numarComponente);
        }
    }

    fout<<numarComponente<<'\n';

    for(int i{1}; i <= numarComponente; i++)
    {
        for(auto nod : componenteConexe[i])
        {
            fout<< nod <<' ';
        }
        fout<<'\n';
    }

    return 0;
}