Cod sursa(job #2971491)

Utilizator SerbanCaroleSerban Carole SerbanCarole Data 27 ianuarie 2023 14:30:23
Problema Componente tare conexe Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.14 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <bitset>
using namespace std;

ifstream cin("ctc.in");
ofstream cout("ctc.out");

const int MAX = 1e5 + 1;

vector <int> g[MAX];

int n , m , topo[MAX] , x , y , k , counter;

bitset <MAX> b;

vector <vector <int> > ans;

vector <int> aux;

void dfst( int x ){

    b[x] = 1;

    for(auto it : g[x]){

        if(!b[it]) dfst(it);
    }

    topo[++k] = x;
}

void dfs( int x ){

    b[x] = 0;

    aux.push_back(x);

    for(auto it : g[x]){

        if(b[it]) dfs(it);
    }

}

int main(){

    cin >> n >> m;

    while(m--){

        cin >> x >> y;

        g[x].push_back(y);
    }

    for(int i = 1 ; i <= n ; i++){

        if(!b[i]) dfst(i);
    }

    for(int i = 1 ; i <= n ; i++){

        if(b[topo[i]]){

            dfs(topo[i]);

            ans.push_back(aux);

            counter++;

            aux.clear();
        }
    }

    cout << counter << '\n';

    for(auto it : ans){

        for(auto i : it){

            cout << i << ' ';
        }

        cout << '\n';
    }

    return 0;
}