Cod sursa(job #2589343)

Utilizator Hidden.bdBurlacu Doru Hidden.bd Data 26 martie 2020 10:57:37
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.34 kb
#include <iostream>
#include <vector>

using namespace std;

#define cin fin
#define cout fout

int n, m, t;
bool ver[10002],vr[10002];
vector <int> c[10002];
vector <int> c2[10002];
vector <int> st;
vector <int> afis[10002];

void DFS( int x ){
    ver[x] = 1;
    
    for( int i = 0 ; i < c[x].size() ; ++i ){
        if( !ver[c[x][i]] ){
            DFS(c[x][i]);
        }
    }
    
    st.push_back(x);
} 

void DFS2( int x ){
    vr[x] = 1;
    
    afis[t].push_back(x);
    for( int i = 0 ; i < c2[x].size() ; ++i ){
        
        if( !vr[c2[x][i]] ){
            DFS2(c2[x][i]);
        }
        
    }
        
}

int main() {
    
    cin >> n >> m;
    for( int i = 1 ; i <= m ; ++i ){
        int x, y;
        cin >> x >> y;
        
        c[x].push_back(y);
        c2[y].push_back(x);
    }
    
    for( int i = 1 ; i <= n ; ++i ){
       if( ver[i] == 0 ){
          DFS(i);
       } 
    }
    
    for( int i = st.size() - 1 ; i >= 0 ; --i ){
        if( vr[st[i]] == 0 ){
            ++t;
            DFS2(st[i]);
        }
    }
    
    cout << t << "\n";
    for( int i = 1 ; i <= t ; ++i ){
        for( int j = 0 ; j < afis[i].size() ; ++j ){
            cout << afis[i][j] << " ";
        }
        cout << '\n';
    }
    
        
    
    
    return 0;
}