Cod sursa(job #3372446)

Utilizator david18.6yDavid Popa david18.6y Data 3 noiembrie 2026 22:21:55
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.73 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

vector<vector<int>> lista, lista_inversa;
vector<int> ordine_terminare;
vector<int> bloc_momentan;
vector<bool> vizitat;

void dfs(int nod) {
    vizitat[nod] = true;
    for (int vecin : lista[nod]) {
        if (vizitat[vecin] == false) {
            dfs(vecin);
        }
    }
    ordine_terminare.push_back(nod);
}

void dfs_inversat(int nod) {
    vizitat[nod] = true;
    bloc_momentan.push_back(nod);
    for (int vecin : lista_inversa[nod]) {
        if (vizitat[vecin] == false) {
            dfs_inversat(vecin);
        }
    }
}

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

    int N, M;
    fin >> N >> M;
    lista.resize(N + 1);
    lista_inversa.resize(N + 1);
    for (int i = 0; i < M; i++) {
        int x, y;
        fin >> x >> y;
        lista[x].push_back(y);
        lista_inversa[y].push_back(x);
    }

    // ctc(lista, lista_inversa)
    vizitat.assign(N + 1, false);
    for (int nod = 1; nod < (int)lista.size(); nod++) {
        if (!vizitat[nod]) {
            dfs(nod);
        }
    }

    vizitat.assign(N + 1, false);

    vector<vector<int>> componente;
    for (int i = (int)ordine_terminare.size() - 1; i >= 0; i--) {
        int nod = ordine_terminare[i];
        if (vizitat[nod] == false) {
            bloc_momentan.clear();
            dfs_inversat(nod);
            componente.push_back(bloc_momentan);
        }
    }

    fout << componente.size() << "\n";
    for (auto &comp : componente) {
        sort(comp.begin(), comp.end());
        for (int x : comp) fout << x << " ";
        fout << "\n";
    }
    return 0;
}