Cod sursa(job #3371645)

Utilizator IeremiaNicolaescu Ieremia Ieremia Data 31 octombrie 2026 11:04:48
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.78 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

// Deschidem fișierele de intrare și ieșire
ifstream fin("ctc.in");
ofstream fout("ctc.out");

const int NMAX = 100005;

// g[u]  = lista de adiacență a grafului orientat original (x -> y)
// gt[u] = lista de adiacență a grafului transpus / inversat (y -> x)
vector<int> g[NMAX], gt[NMAX]; 

// stiva = va reține nodurile în ordinea finalizării parcurgerii din primul DFS
// ctc   = ctc[i] va conține toate nodurile din componenta tare conexă cu numărul i
vector<int> stiva, ctc[NMAX];  

bool viz[NMAX]; // Vector de frecvență pentru a marca nodurile vizitate
int n, m, nr_ctc;

// --- PASUL 1: Primul DFS pe graful original ---
// Scopul este de a adăuga nodurile în "stivă" pe măsură ce terminăm de vizitat toți vecinii lor (postordine)
void dfs1(int u) {
    viz[u] = true;
    for (int v : g[u]) {
        if (!viz[v]) {
            dfs1(v);
        }
    }
    stiva.push_back(u); // Adăugăm u în stivă DUPĂ ce am explorat toți vecinii
}

// --- PASUL 2: Al doilea DFS pe graful transpus ---
// Mergem înapoi pe muchiile inversate. Marchează nodurile din aceeași CTC ca nevizitate (viz[u] = false)
void dfs2(int u) {
    viz[u] = false; // Demarcăm nodul ca să știm că l-am inclus deja într-o CTC
    ctc[nr_ctc].push_back(u); // Adăugăm nodul în componenta curentă

    for (int v : gt[u]) {
        if (viz[v]) { // Dacă vecinul a fost vizitat în primul DFS și nu a fost procesat încă
            dfs2(v);
        }
    }
}

int main() {
    fin >> n >> m;
    while (m--) {
        int x, y;
        fin >> x >> y;
        g[x].push_back(y);   // Muchia orientată originală: x -> y
        gt[y].push_back(x);  // Muchia inversată pentru graful transpus: y -> x
    }

    // 1. Rulăm DFS1 pe graful original pentru a umple stiva cu ordinea de terminare
    for (int i = 1; i <= n; i++) {
        if (!viz[i]) {
            dfs1(i);
        }
    }

    // 2. Parcurgem stiva de la coadă la cap (de la nodul care s-a terminat ultimul)
    for (int i = stiva.size() - 1; i >= 0; i--) {
        int u = stiva[i];
        // Dacă nodul u este încă vizitat (true), înseamnă că nu face parte din nicio CTC creată anterior
        if (viz[u]) {
            nr_ctc++; // Am găsit o nouă componentă tare conexă
            dfs2(u);  // Adunăm toate nodurile din această componentă folosind graful transpus
        }
    }

    // 3. Afișăm numărul total de componente tare conexe
    fout << nr_ctc << "\n";

    // 4. Afișăm nodurile fiecărei componente
    for (int i = 1; i <= nr_ctc; i++) {
        for (int v : ctc[i]) {
            fout << v << " ";
        }
        fout << "\n";
    }

    return 0;
}