Cod sursa(job #3339204)

Utilizator Furtuna_LucaFurtuna Luca Furtuna_Luca Data 6 februarie 2026 19:09:54
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.4 kb
#include <bits/stdc++.h>
#define NMAX 100002

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

int n, m, nrc;
bool uz[NMAX];

stack <int> ctc;
vector <int> muchii[NMAX];
vector <int> muchii_inv[NMAX];
vector <int> afis[NMAX];

void fdfs(int x);
void sdfs(int x);
void kosaraju();

int main()
{
    int i, x, y;
    fin >> n >> m;
    while(fin >> x >> y)
       {
           muchii[x].push_back(y);
           muchii_inv[y].push_back(x); ///graful inversat
       }

    kosaraju();

    fout << nrc << '\n';
    for(i = 1; i <= nrc; i++)
    {
        for(auto j : afis[i])
            fout << j << ' ';
        fout << '\n';
    }
    return 0;
}

void fdfs(int x)
{
    int i;
    uz[x] = true;
    for(auto i : muchii[x])
        if(!uz[i])
            fdfs(i);
    ctc.push(x);

}

void sdfs(int x)
{
    int i;
    uz[x] = true;
    afis[nrc].push_back(x);
    for(auto i : muchii_inv[x])
        if(!uz[i])
            sdfs(i);
}

void kosaraju()
{
    int i;
    ///construiesc stiva
    for(i = 1; i <= n; i++)
        if(!uz[i])
            fdfs(i);
    ///resetez uz
    for(i = 1; i <= n; i++)
        uz[i] = false;
    ///aflu componentele tare conexe
    while(!ctc.empty())
    {
        i = ctc.top();
        ctc.pop();
        if(!uz[i])
        {
            nrc++;
            sdfs(i);
        }
    }
}