Cod sursa(job #3374907)

Utilizator teogrecigrecioiu teo teogreci Data 9 noiembrie 2026 18:31:32
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.43 kb
#include <fstream>
#include <vector>
using namespace std;

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

const int nmax = 100005;
int n, m;
vector<int> g[nmax];
vector<int> gt[nmax];
bool vizitat[nmax];
int ordine[nmax];
int nrOrdine;

vector<int> componente[nmax];
int nrComponente;

void dfs1(int x) {
    vizitat[x] = true;
    for (int k = 0; k < (int)g[x].size(); k++) {
        int y = g[x][k];
        if (!vizitat[y])
            dfs1(y);
    }
    ordine[++nrOrdine] = x;
}
void dfs2(int x) {
    vizitat[x] = true;
    componente[nrComponente].push_back(x);
    for (int k = 0; k < (int)gt[x].size(); k++) {
        int y = gt[x][k];
        if (!vizitat[y])
            dfs2(y);
    }
}

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

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

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

    for (int i = n; i >= 1; i--) {
        int x = ordine[i];
        if (!vizitat[x]) {
            nrComponente++;
            dfs2(x);
        }
    }
    fout << nrComponente << "\n";
    for (int i = 1; i <= nrComponente; i++) {
        for (int j = 0; j < (int)componente[i].size(); j++)
            fout << componente[i][j] << " ";
        fout << "\n";
    }
    return 0;
}