Cod sursa(job #3374063)

Utilizator mattiaslupuLupu Mattias Andrea mattiaslupu Data 8 noiembrie 2026 16:59:55
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.67 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");

int n, m;

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

    for (int vecin : lista[nod]) {
        if (!vizitat[vecin]) {
            dfs1(vecin, lista, vizitat, ordine);
        }
    }

    ordine.push_back(nod);
}

void dfs2(int nod, const vector<vector<int>>& listaInversa,
          vector<int>& vizitat, vector<int>& componenta) {
    vizitat[nod] = 1;
    componenta.push_back(nod);

    for (int vecin : listaInversa[nod]) {
        if (!vizitat[vecin]) {
            dfs2(vecin, listaInversa, vizitat, componenta);
        }
    }
}

int main() {
    f>>n>>m;
    vector<vector<int>> lista1(n+1);
    vector<vector<int>> lista2(n+1);

    for (int i=0; i<m; i++) {
        int x, y;
        f>>x>>y;
        lista1[x].push_back(y);
        lista2[y].push_back(x);
    }
    vector<int> vizitat(n+1, 0);
    vector<int> ordine;

    for (int i=1; i<=n; i++) {
        if (!vizitat[i]) {
            dfs1(i, lista1, vizitat, ordine);
        }
    }
    fill(vizitat.begin(), vizitat.end(), 0);
    vector<vector<int>> componente;
    for (int i=n-1; i>=0; i--) {
        int nod = ordine[i];

        if (!vizitat[nod]) {
            vector<int> componenta;
            dfs2(nod, lista2, vizitat, componenta);
            componente.push_back(componenta);
        }
    }
    g<<componente.size() << '\n';
    for (vector<int> &componenta : componente) {
        for (int nod : componenta) {
            g<<nod<<' ';
        }
        g<<'\n';
    }

    return 0;
}