Cod sursa(job #3372370)

Utilizator GrigoreAlexandraGrigore Alexandra GrigoreAlexandra Data 3 noiembrie 2026 13:26:51
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.5 kb
// O(N + M)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

const int NMAX = 100005;

vector<int> adj[NMAX];
vector<int> transpus[NMAX];

vector<int> ordine;
vector<int> componente[NMAX];

bool viz[NMAX];
int nrCTC = 0;

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

    for (int vecin : adj[nod])
    {
        if (!viz[vecin])
            dfs1(vecin);
    }
    // pus dupa vecini -> cel mai lung drum
    ordine.push_back(nod);
}

void dfs2(int nod)
{
    viz[nod] = true;
    componente[nrCTC].push_back(nod);

    for (int vecin : transpus[nod])
    {
        if (!viz[vecin])
            dfs2(vecin);
    }
}

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

    if (!fin || !fout) return 1;

    int n, m;
    fin >> n >> m;

    for (int i = 1; i <= m; i++)
    {
        int x, y;
        fin >> x >> y;

        adj[x].push_back(y);
        transpus[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 = (int)ordine.size() - 1; i >= 0; i--)
    {
        int nod = ordine[i];

        if (!viz[nod])
        {
            nrCTC++;
            dfs2(nod);
        }
    }

    fout << nrCTC << '\n';

    for (int i = 1; i <= nrCTC; i++)
    {
        for (int nod : componente[i])
            fout << nod << " ";

        fout << '\n';
    }

    return 0;
}