Cod sursa(job #3371067)

Utilizator ArcopieBirghilescu Alexandru Arcopie Data 28 octombrie 2026 13:44:26
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.8 kb
//
// Created by Admin on 10/28/2026.
//
#include <bits/stdc++.h>
using namespace std;

ifstream intrare("ctc.in");
ofstream iesire("ctc.out");

const int MAX_NODURI = 100005;
int nr_noduri, nr_muchii, nr_ctc;

vector<int> ordine_iesire, id_ctc;
vector<vector<int>> graf, graf_transpus, componente;
bitset<MAX_NODURI> vizitat;

void parcurgere_dfs(int nod) {
    vizitat[nod] = 1;
    for (int vecin : graf[nod])
        if (!vizitat[vecin])
            parcurgere_dfs(vecin);
    ordine_iesire.push_back(nod);
}

void parcurgere_dfs_transpus(int nod) {
    vizitat[nod] = 1;
    id_ctc[nod] = nr_ctc;
    for (int vecin : graf_transpus[nod])
        if (!vizitat[vecin])
            parcurgere_dfs_transpus(vecin);
}

void AlgoritmulKosaraju() {
    for (int i = 1; i <= nr_noduri; i++)
        if (!vizitat[i])
            parcurgere_dfs(i);

    reverse(ordine_iesire.begin(), ordine_iesire.end());
    vizitat.reset();
    id_ctc.resize(nr_noduri + 1);

    for (int nod : ordine_iesire)
        if (!vizitat[nod]) {
            nr_ctc++;
            parcurgere_dfs_transpus(nod);
        }

    componente.resize(nr_ctc + 1);
    for (int i = 1; i <= nr_noduri; i++)
        componente[id_ctc[i]].push_back(i);
}

int main() {
    intrare >> nr_noduri >> nr_muchii;
    graf.resize(nr_noduri + 1);
    graf_transpus.resize(nr_noduri + 1);

    for (int i = 1; i <= nr_muchii; i++) {
        int sursa, destinatie;
        intrare >> sursa >> destinatie;
        graf[sursa].push_back(destinatie);
        graf_transpus[destinatie].push_back(sursa);
    }

    AlgoritmulKosaraju();

    iesire << nr_ctc << '\n';
    for (int i = 1; i <= nr_ctc; i++) {
        for (int nod : componente[i])
            iesire << nod << ' ';
        iesire << '\n';
    }
    return 0;
}