Cod sursa(job #3212062)

Utilizator KarinaDKarina Dumitrescu KarinaD Data 11 martie 2024 01:51:44
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.51 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

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

const int N = 1e5;

vector <int> g[N + 10];
vector <int> gInv[N + 10];

vector <int> st;

vector <int> comp[N + 10];

int viz[N + 10];

int sort_top ( int node ) {
    
    viz[node] = 1;
    
    for ( int i = 0; i < g[node].size(); i++ )
        if ( viz[g[node][i]] == 0 )
            sort_top (g[node][i]);
    
    st.push_back (node);
    
    return 0;
}

int ctc ( int node, int val ) {
    
    viz[node] = 1;
    
    for ( int i = 0; i < gInv[node].size(); i++ )
        if ( viz[gInv[node][i]] == 0 )
            ctc (gInv[node][i], val);
    
    comp[val].push_back (node);
    
    return 0;
}

int main () {
    
    int n, m, x, y;
    
    fin >> n >> m;
    
    for ( int i = 0; i < m; i++ ) {
        
        fin >> x >> y;
        
        g[x].push_back (y);
        gInv[y].push_back (x);
    }
    
    for ( int i = 1; i <= n; i++ )
        if ( viz[i] == 0 )
            sort_top (i);
    
    reverse ( st.begin() , st.end() );
    
    for ( int i = 1; i <= n; i++ )
        viz[i] = 0;
    
    int cnt = 0;
    
    for ( int i = 0; i < n; i++ ) {
        if ( viz[st[i]] == 0 ) {
            cnt++;
            ctc ( st[i], cnt );
        }
    }
    
    fout << cnt << "\n";
    
    for ( int i = 1; i <= cnt; i++ ) {
        for ( int j = 0; j < comp[i].size(); j++ )
            fout << comp[i][j] << " ";
        fout << "\n";
    }
    
    return 0;
}