Cod sursa(job #2928192)

Utilizator liviu_gheorghe1234Liviu Gheorghe liviu_gheorghe1234 Data 22 octombrie 2022 13:23:00
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.99 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <sstream> 
using namespace std;

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

vector<int>* adjListG;
vector<int>* adjListGT;
bool* visited;
stack<int> nodes;
std::stringstream ssResult;

void DFS(int currentNode) {

    //cout << currentNode << " "; 

    visited[currentNode] = true;

    for(int i = 0; i<adjListG[currentNode].size(); i++) {
        if(!visited[adjListG[currentNode][i]]) {
            DFS(adjListG[currentNode][i]);
        }
    }
    nodes.push(currentNode);
}


void DFST(int currentNode) {
    
    ssResult << currentNode << " ";

    visited[currentNode] = true;

    for(int i = 0; i<adjListGT[currentNode].size(); i++) {
        if(!visited[adjListGT[currentNode][i]]) {
            DFST(adjListGT[currentNode][i]);
        }
    }

}

int main() {

    int N, M, x, y;
    fin >> N >> M;

    adjListG = new vector<int>[N+1];
    adjListGT = new vector<int>[N+1];
    visited = new bool[N+1];

    for(int i = 0; i<N;i++) {
        visited[i] = false;
    }


    for(int i = 0; i<M;++i) {
        fin >> x >> y;
        adjListG[x].push_back(y);
        adjListGT[y].push_back(x);
    }

    // Print adj list

    // for(int i = 1; i<=N; i++) {
    //     for(int j = 0; j < adjListG[i].size(); j++) {
    //         cout << adjListG[i][j] << " ";
    //     }
    //     cout << "\n";
    // }


    for(int i = 1; i <= N; i++) {
        if(!visited[i]) {
            DFS(i);
        }
    }

    for(int i = 0; i<=N;i++) {
        visited[i] = false;
    }

    // cout << "\n---\n";
    // for(int i = 0; i<N;i++) {
    //     cout << visited[i] << " ";
    // }
    // cout << "\n---\n";


    int nrComp = 0;

    while(!nodes.empty()) {
        int currentNode = nodes.top();
        nodes.pop();
        if(!visited[currentNode]) {
            DFST(currentNode);
            ++nrComp;
            ssResult << "\n";
        }
    }

    fout << nrComp << "\n";
    fout << ssResult.rdbuf();

    return 0; 
}