Cod sursa(job #3374673)

Utilizator irina_maneaIrina Manea irina_manea Data 9 noiembrie 2026 08:58:14
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.67 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

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

int n, m;
vector<vector<int> > lista;
vector<vector<int> > listaInversa;
vector<vector<int> > componente;

vector<bool> vizitat;
vector<int> ordine;

void citire() {
    f >> n >> m;

    lista.resize(n + 1);
    listaInversa.resize(n + 1);
    vizitat.resize(n + 1, false);

    for (int i = 0; i < m; i++) {
        int x, y;
        f >> x >> y;
        lista[x].push_back(y);
        listaInversa[y].push_back(x);
    }
}

void dfsNormal(int nod) {
    vizitat[nod] = true;

    for (int i = 0; i < lista[nod].size(); i++) {
        int vecin = lista[nod][i];
        if (vizitat[vecin] == false) {
            dfsNormal(vecin);
        }
    }

    ordine.push_back(nod);
}

void dfsInvers(int nod) {
    vizitat[nod] = false;
    componente.back().push_back(nod);

    for (int i = 0; i < listaInversa[nod].size(); i++) {
        int vecin = listaInversa[nod][i];
        if (vizitat[vecin] == true) {
            dfsInvers(vecin);
        }
    }
}

void afisare() {
    g << componente.size() << "\n";

    for (int i = 0; i < componente.size(); i++) {
        for (int j = 0; j < componente[i].size(); j++) {
            g << componente[i][j] << " ";
        }
        g << "\n";
    }
}

int main() {
    citire();

    for (int i = 1; i <= n; i++) {
        if (vizitat[i] == false) {
            dfsNormal(i);
        }
    }

    for (int i = ordine.size() - 1; i >= 0; i--) {
        int nod = ordine[i];
        if (vizitat[nod] == true) {
            componente.push_back(vector<int>());
            dfsInvers(nod);
        }
    }

    afisare();

    return 0;
}