Cod sursa(job #3374672)

Utilizator irina_maneaIrina Manea irina_manea Data 9 noiembrie 2026 08:56:32
Problema Componente tare conexe Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.81 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<bool> vizitat;
vector<int> ordine;

vector<int> componentaNodului;
int nrComponente;

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

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

    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] = true;
    componentaNodului[nod] = nrComponente;

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

void afisare() {
    g << nrComponente << "\n";

    for (int c = 1; c <= nrComponente; c++) {
        for (int nod = 1; nod <= n; nod++) {
            if (componentaNodului[nod] == c) {
                g << nod << " ";
            }
        }
        g << "\n";
    }
}

int main() {
    citire();

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

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

    for (int i = ordine.size() - 1; i >= 0; i--) {
        int nod = ordine[i];
        if (vizitat[nod] == false) {
            nrComponente++;
            dfsInvers(nod);
        }
    }

    afisare();

    return 0;
}