Cod sursa(job #3373704)

Utilizator srares2006Samoila Rares srares2006 Data 7 noiembrie 2026 17:00:53
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.02 kb
#include <fstream>
#include <vector>
using namespace std;

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

const int NMAX = 100001;

vector<int> graf[NMAX]; // arcele din graful original
vector<int> transpus[NMAX]; // aceleasi arce, cu sensul inversat
vector<int> ordine; // ordinea in care terminam explorarea nodurilor
bool vizitat[NMAX];
vector<int> componente[NMAX]; // componente[i] contine nodurile din componenta i
int nrComponente = 0;

void dfsOrdine(int u)
{
    vizitat[u] = true;
    // exploram vecinii lui u in graful original
    for (int v : graf[u])
    {
        if (!vizitat[v])
            dfsOrdine(v);
    }
    ordine.push_back(u);// il adaugam pe u abia dupa ce am terminat de explorat vecinii lui
}

void dfsComponenta(int u)
{
    vizitat[u] = true;
    componente[nrComponente].push_back(u);// u face parte din componenta pe care o construim acum
    // continuam cautarea pe arcele inversate
    for (int v : transpus[u])
    {
        if (!vizitat[v])
            dfsComponenta(v);
    }
}

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

    // primul DFS trebuie sa ajunga la toate nodurile, inclusiv cele izolate
    for (int u = 1; u <= n; u++)
    {
        if (!vizitat[u])
            dfsOrdine(u);
    }

    // stergem marcajele
    for (int u = 1; u <= n; u++)
        vizitat[u] = false;

    // incepem cu nodul a carui explorare s-a terminat ultima
    for (int i = n - 1; i >= 0; i--)
    {
        int u = ordine[i];

        if (!vizitat[u])
        {
            // fiecare DFS nou pe graful transpus gaseste o componenta
            nrComponente++;
            dfsComponenta(u);
        }
    }
    fout << nrComponente << '\n';
    for (int i = 1; i <= nrComponente; i++)
    {
        for (int u : componente[i])
            fout << u << ' ';

        fout << '\n';
    }

    return 0;
}