Cod sursa(job #3374481)

Utilizator cristian___Nastase Cristian-Florin cristian___ Data 9 noiembrie 2026 01:09:30
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.66 kb
#include <fstream>
#include <vector>

using namespace std;

void dfs(int nod, const vector<vector<int>>& lista, vector<int>& visited, vector<int>& ordine) {
    visited[nod] = 1;

    for (auto vecin : lista[nod]) {
        if (!visited[vecin]) {
            dfs(vecin, lista, visited, ordine);
        }
    }

    ordine.push_back(nod);
}

void dfsInversat(int nod, const vector<vector<int>>& lista, vector<int>& visited, vector<int>& componenta) {
    visited[nod] = 1;
    componenta.push_back(nod);

    for (auto vecin : lista[nod]) {
        if (!visited[vecin]) {
            dfsInversat(vecin, lista, visited, componenta);
        }
    }
}

int main() {
    ifstream in("ctc.in");
    ofstream out("ctc.out");

    int n, m, x, y;
    in>>n>>m;

    vector<vector<int>> lista(n + 1);
    vector<vector<int>> listaInversata(n + 1);

    while (in>>x>>y) {
        lista[x].push_back(y);
        listaInversata[y].push_back(x);
    }

    vector<int> visited(n + 1, 0);
    vector<int> ordine;

    for (int nod = 1; nod <= n; nod++) {
        if (!visited[nod]) {
            dfs(nod, lista, visited, ordine);
        }
    }

    visited.resize(0);
    visited.resize(n+1, 0);

    vector<vector<int>> componente;

    for (int i = n - 1; i >= 0; i--) {
        int nod = ordine[i];

        if (!visited[nod]) {
            vector<int> componentaCurenta;
            dfsInversat(nod, listaInversata, visited, componentaCurenta);
            componente.push_back(componentaCurenta);
        }
    }

    out<<componente.size()<<'\n';

    for (auto componenta : componente) {
        for (int nod : componenta) {
            out<<nod<<' ';
        }
        out<<'\n';
    }

    return 0;
}