Cod sursa(job #3375720)

Utilizator Andrei1209Andrei Mircea Andrei1209 Data 13 noiembrie 2026 10:22:34
Problema Componente tare conexe Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.38 kb
#include <fstream>
#include <vector>

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

const int Nmax = 1e5 +5;
vector <int> vecini[Nmax], l, vecini_transpus[Nmax];
int viz[Nmax];
vector <int> sol[Nmax];
void ordine( int nod )
{
    if ( viz[nod] )
        return ;
    viz[nod] = 1;

    for ( int i = 0; i < vecini[nod].size(); ++i )
        ordine( vecini[nod][i] );

    l.push_back( nod );
}
void CTC( int nod, int cod )
{
    if ( viz[nod] )
        return ;

    viz[nod] = cod;
    for ( int vecin : vecini_transpus[nod] )
    {
        CTC(vecin, cod);
    }
}
int main()
{
    int n, m;
    fin >> n >> m;

    int i;
    for ( i = 1; i <= m; ++i )
    {
        int a, b;
        fin >> a >> b;
        vecini[a].push_back(b);
        vecini_transpus[b].push_back(a);
    }
    for ( i = 1; i <= n; ++i )
        ordine(i);

    for ( i = 1; i <= n; ++i )
        viz[i] = 0;
    int cnt =0;

    for ( i = l.size() - 1; i >= 0; --i )
    {
        if ( viz[l[i]] == 0 )
        {
            ++cnt;
            CTC(l[i], cnt);
        }
    }
    fout << cnt << '\n';
    return 0;
    for ( i = 1; i <= n; ++i )
        sol[  viz[i] ].push_back(i);

    for ( i = 1; i <= cnt; ++i )
    {
        for ( int nod : sol[i] )
            fout << nod << " ";
        fout << '\n';
    }

    return 0;
}