Cod sursa(job #3371816)

Utilizator ursus161Stefan Ghetu ursus161 Data 31 octombrie 2026 22:00:34
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.38 kb
#include <bits/stdc++.h>

std::vector<std::vector<int>> graf, grafT;
std::vector<int> comp;              // comp[i] = componenta lui i, 
std::vector<bool> plus;
std::vector<int> ordine;            // nodurile in ord care termina
int nr = 0;

// unde pot ajunge din nod
void dfs(int nod) {
    plus[nod] = true;
    for (int v : graf[nod])
        if (!plus[v])
            dfs(v);
    ordine.push_back(nod);
}

 
void dfsMinus(int nod) {
    comp[nod] = nr;
    for (int v : grafT[nod])
        if (comp[v] == 0)
            dfsMinus(v);
}

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

    int n, m;
    fin >> n >> m;
    graf.resize(n + 1);
    grafT.resize(n + 1);
    comp.resize(n + 1, 0);

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

    plus.assign(n + 1, false);
    for (int x = 1; x <= n; x++)
        if (!plus[x]) dfs(x);

    for (int i = n - 1; i >= 0; i--) {    
        int x = ordine[i];
        if (comp[x] != 0) continue;   // x e deja într-o componenta

        nr++;
        dfsMinus(x);
    }

    std::vector<std::vector<int>> noduri(nr + 1);
    for (int i = 1; i <= n; i++)
        noduri[comp[i]].push_back(i);

    fout << nr << "\n";
    for (int c = 1; c <= nr; c++) {
        for (int i : noduri[c]) fout << i << " ";
        fout << "\n";
    }
}