Cod sursa(job #3201978)

Utilizator dobreraduDobre Radu Fabian dobreradu Data 10 februarie 2024 11:38:02
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.29 kb
#include <bits/stdc++.h>

using namespace std;
ifstream in("ctc.in");
ofstream out("ctc.out");
vector <int> sortaret;
vector <vector <int> > g, inv, componenta;
int grade[100005];
bool viz[100005];
int cnt;
void dfs( int nod ){
    viz[nod] = true;
    for( auto vec : g[nod] )
        if( !viz[vec] )
            dfs( vec );
    sortaret.push_back(nod);
}
void ctc( int nod ){
    viz[nod] = true;
    for( auto vec : inv[nod] )
        if( !viz[vec] ) 
            ctc( vec );
    componenta[cnt].push_back(nod);
}
int main()
{
    int n, m;
    in >> n >> m;
    g.resize(n+1);
    inv.resize(n+1);
    for( int i = 0; i < m; i++ ){
        int a, b;
        in >> a >> b;
        g[a].push_back(b);
        inv[b].push_back(a);
        grade[b]++;
    }
    for( int i = 1; i <= n; i++ )
        if( !viz[i] )
            dfs(i);
    for( int i = 1; i <= n; i++ )
        viz[i] = false;
    reverse(sortaret.begin(), sortaret.end());
    for( auto x : sortaret ){
        if( !viz[x] ){
            componenta.resize(componenta.size()+1);
            ctc(x);
            cnt++;
        }
    }
    out << componenta.size() << "\n";
    for( auto x : componenta ){
        for( auto y : x )
            out << y << " ";
        out << "\n";
    }
    return 0;
}