Cod sursa(job #2928985)

Utilizator adeladanescuAdela Danescu adeladanescu Data 24 octombrie 2022 12:46:26
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.53 kb
#include<iostream>
#include<fstream>
#include<vector>
#include<stack>

using namespace std;

vector<int> G[100002],T[100002],C[100002];
int N, M, nr, x, y, vizitat[100002];
stack<int> stiva;


void dfs(int Nod) //dfs pe nodurile grafului
{
    vizitat[Nod] = 1;
    for( int i=0; i<G[Nod].size();i++) {

        if(vizitat[G[Nod][i]] == 0)
            dfs(G[Nod][i]);
    }

    stiva.push(Nod); //punem nodurile pe stiva, pentru a putea retine ordinea inversa
}

void dfs_2(int Nod) //dfs pe nodurile transpusei
{
    vizitat[Nod] = 2;
    for(int i=0; i < T[Nod].size(); i++) {

        if(vizitat[T[Nod][i]] == 1)
            dfs_2(T[Nod][i]);
    }

    C[nr].push_back(Nod); //adaugam nodul la componenta conexa
}

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

int main()
{
    fin >> N >> M;
    for(int i = 1; i <= M; i++)
    {
        //construim graful si transpusa garfului
        fin >> x >> y;
        G[x].push_back(y);
        T[y].push_back(x);
    }


    for(int i=1;i<=N;i++)
        if(vizitat[i] == 0)
            dfs(i);  //apelam dfs pt nodurile grafului

    while(stiva.empty()==0) {
        //scoatem cate un nod de pe stiva, obtinand astfel ordinea inversa a acestora
        if (vizitat[stiva.top()] == 1) {
            nr++;              //creste nr-ul de componente conexe
            dfs_2(stiva.top());
        }
        stiva.pop();
    }



    fout << nr << "\n";
    for(int i = 1; i <= nr; i++) {
        for(int j = 0; j < C[i].size(); j++)
            fout << C[i][j] << " ";
        fout<<"\n";
    }
    return 0;
}