Cod sursa(job #3374084)

Utilizator anastasia.sAnastasia anastasia.s Data 8 noiembrie 2026 17:22:26
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.53 kb
#include <fstream>
#include <iostream>
#include <vector>

using namespace std;

#define NMax 100005
vector<int> g[NMax];
vector<int> gt[NMax];
bool viz[NMax];
vector<int> st;
vector<vector<int>> ctc;

void dfs1(int nod) {
    viz[nod] = true;

    for (int vecin : g[nod])
        if (viz[vecin] == false)
            dfs1(vecin);

    st.push_back(nod);
}

void dfs2(int nod, vector<int>& componenta) {
    viz[nod] = true;

    componenta.push_back(nod);  // adaugam nodul in componenta
    for (int vecin : gt[nod])   // parcurgem vecinii lui nod din graful transpus
        if (viz[vecin] == false)
            dfs2(vecin, componenta);
}

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

    int n, m;
    fin >> n >> m;
    int x, y;
    for (int i = 0; i < m; i++) {
        fin >> x >> y;
        g[x].push_back(y);
        gt[y].push_back(x);
    }

    for (int i = 1; i <= n; i++)
        if (!viz[i])
            dfs1(i);

    for (int i = 1; i <= n; i++)
        viz[i] = false;

    for (int i = st.size() - 1; i >= 0; i--) {
        int nod = st[i];  // extragem cel mai de sus nod din stiva
        if (viz[nod] == false) { // daca nu e viz, inseamna ca am dat peste o noua ctc
            vector<int> componenta;
            dfs2(nod, componenta);
            ctc.push_back(componenta);
        }
    }

    fout << ctc.size() << "\n";
    for(auto c : ctc) {
        for (auto el : c)
            fout << el << " ";
        fout << "\n";
    }

    return 0;
}