Cod sursa(job #3374910)

Utilizator tenirinaIrina Tenita tenirina Data 9 noiembrie 2026 18:51:41
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.87 kb
#include <fstream>
#include <vector>

using namespace std;

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

int n, m;
vector<int> graf[100001];          // graf[x] nodurile in care se ajung din x
vector<int> transpus[100001];      // cu toate muchiile intoarse
vector<int> ordine;                // nodurile in ordinea in care se termina de vizitat
vector<int> componente[100001];    // componente[c] nodurile componentei c
bool vizitat[100001];
int nr_componente;

void dfs_graf(int nod)
{
    vizitat[nod] = true;
    for (int vecin : graf[nod])
        if (!vizitat[vecin])
            dfs_graf(vecin);
    ordine.push_back(nod);         // nodul se pune in lista dupa ce am vizitat tot ce se poate din el
}

void dfs_transpus(int nod)
{
    vizitat[nod] = true;
    componente[nr_componente].push_back(nod);
    for (int vecin : transpus[nod])
        if (!vizitat[vecin])
            dfs_transpus(vecin);
}

int main()
{
    in >> n >> m;
    for (int k = 1; k <= m; k++)
    {
        int x, y;
        in >> x >> y;
        graf[x].push_back(y);
        transpus[y].push_back(x);  // muchia intoarsa
    }

    // pas 1 parcurgem graful si retinem ordinea in care se termina nodurile
    for (int i = 1; i <= n; i++)
    {
        if (!vizitat[i])
            dfs_graf(i);
    }
    for (int i = 1; i <= n; i++)
    {
        vizitat[i] = false;
    }
    // pas 2 luam nodurile in ordine inversa si parcurgem graful transpus
    for (int i = n-1; i >= 0; i--)
    {
        int nod = ordine[i];
        if (!vizitat[nod])
        {
            nr_componente++;
            dfs_transpus(nod);
        }
    }
    out << nr_componente << "\n";
    for (int c = 1; c <= nr_componente; c++)
    {
        for (int nod : componente[c])
        {
            out << nod << " ";
        }
        out << "\n";
    }
    return 0;
}