Cod sursa(job #2929536)

Utilizator ScoveargaIlie Andrei-Virgil Scovearga Data 26 octombrie 2022 00:01:17
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.35 kb
#include <iostream>
#include <fstream>
#include <stack>
#include <vector>

using namespace std;

ifstream f("ctc.in");
ofstream g("ctc.out");

int N, M, nrComponente, x, y;
bool vizitate[100001], inStiva[100001];
stack <int> stiva;
vector <int> adiacenta[100001], componenteConexe[100001], rev[100001];

void build(int nod)
{
    inStiva[nod] = true;
    for(int urmator : adiacenta[nod])
    {
        if(inStiva[urmator])
            continue;
        build(urmator);
    }
    stiva.push(nod);
}

void dfs(int nod)
{
    vizitate[nod] = true;
    componenteConexe[nrComponente].push_back(nod);

    for(int urmator : rev[nod])
    {
        if(vizitate[urmator])
            continue;
        dfs(urmator);
    }
}

int main()
{
    f>>N>>M;
    for(int i = 0; i < M; i++)
    {
        f>>x>>y;
        adiacenta[x].push_back(y);
        rev[y].push_back(x);
    }

    for(int i = 0; i < N; ++i)
    {
        if(inStiva[i])
            continue;
        build(i);
    }

    while(stiva.size())
    {
        int curent = stiva.top();
        stiva.pop();

        if(vizitate[curent])
            continue;

        ++nrComponente;
        dfs(curent);
    }

    g<<nrComponente<<'\n';
    for(int i = 0; i < nrComponente; ++i)
    {
        for(int nod : componenteConexe[i])
            g<<nod<<' ';
        g<<'\n';
    }

    g.close();
    f.close();
    return 0;
}