Cod sursa(job #3196809)

Utilizator zamfiresqAlexandra Zamfirescu zamfiresq Data 24 ianuarie 2024 20:20:29
Problema Componente tare conexe Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.64 kb
#include <iostream>
#include <fstream>
#include <stack>
#include <vector>


const int MAX_N = 100001;

std::stack<int> stiva;
std::vector<int> listaAdiacenta[MAX_N];
std::vector<std::vector<int> > tareConex;
int id[MAX_N], low[MAX_N], currentId = 1, componentaCount = 0;


// implementare algoritm Tarjan

void DFS(int current) {
    id[current] = currentId;
    low[current] = currentId;
    currentId++;
    stiva.push(current);

    for (int nodVecin : listaAdiacenta[current]) {
        if (id[nodVecin] == 0) {
            DFS(nodVecin);
            low[current] = std::min(low[current], low[nodVecin]);
        } else if (stiva.size() && id[nodVecin] && low[nodVecin]) {
            low[current] = std::min(low[current], id[nodVecin]);
        }
    }

    if (id[current] == low[current]) {
        std::vector<int> componenta;
        int node = stiva.top();
        stiva.pop();

        componenta.push_back(node);
        while (current != node) {
            node = stiva.top();
            stiva.pop();
            componenta.push_back(node);
        }

        tareConex.push_back(componenta);
        componentaCount++;
    }
}

int main() {

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

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

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

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

    fout << componentaCount << '\n';
    for (const auto &componenta : tareConex) {
        for (int node : componenta) {
            fout << node << " ";
        }
        fout << '\n';
    }

    return 0;
}