Cod sursa(job #3374561)

Utilizator gabiaAygan Gabriela Aylin gabia Data 9 noiembrie 2026 02:13:45
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.75 kb
#include <fstream>
#include <vector>
using namespace std;

// Algoritmul lui Tarjan pentru componente tare conexe.
// Facem un DFS si pastram:
//   idx[x]  = momentul la care am intrat prima data in x
//   low[x]  = cel mai mic idx la care se poate ajunge din subarborele lui x
//             (folosind cel mult o muchie care se intoarce in stiva)
// Daca low[x] == idx[x], atunci x este "radacina" unei componente tare conexe:
// scoatem din stiva toate nodurile pana la x, ele formeaza componenta.

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

const int NMAX = 100005;

int n, m;
vector<int> G[NMAX];
int idx[NMAX], low[NMAX];
bool peStiva[NMAX];
int stiva[NMAX], varf;
int timp;
int nrComp;
vector<int> comp[NMAX];

void dfs(int x) {
    timp++;
    idx[x] = low[x] = timp;
    varf++;
    stiva[varf] = x;
    peStiva[x] = true;

    for (size_t k = 0; k < G[x].size(); k++) {
        int y = G[x][k];
        if (idx[y] == 0) {
            dfs(y);
            if (low[y] < low[x])
                low[x] = low[y];
        } else if (peStiva[y]) {
            if (idx[y] < low[x])
                low[x] = idx[y];
        }
    }

    if (low[x] == idx[x]) {
        nrComp++;
        int y;
        do {
            y = stiva[varf];
            varf--;
            peStiva[y] = false;
            comp[nrComp].push_back(y);
        } while (y != x);
    }
}

int main() {
    fin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int x, y;
        fin >> x >> y;
        G[x].push_back(y);
    }

    for (int i = 1; i <= n; i++)
        if (idx[i] == 0)
            dfs(i);

    fout << nrComp << "\n";
    for (int i = 1; i <= nrComp; i++) {
        for (size_t k = 0; k < comp[i].size(); k++)
            fout << comp[i][k] << " ";
        fout << "\n";
    }

    return 0;
}