Cod sursa(job #3002272)

Utilizator SerbanCaroleSerban Carole SerbanCarole Data 14 martie 2023 16:52:08
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.17 kb
#include <fstream>
#include <vector>
using namespace std;

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

const int MAX = 5e4 + 1;

vector <int> g[MAX] , gt[MAX];

int topo[MAX] , in , n , m , x , y;

bool viz[MAX];

vector <vector<int>>ctc;
vector <int> aux;

void dfs( int x ){

    viz[x] = 1;

    for(auto it : g[x]){

        if(!viz[it]){

            dfs(it);
        }
    }

    topo[in--] = x;
}

void dfst( int x ){

    viz[x] = 0;

    aux.push_back(x);

    for(auto it : gt[x]){

        if(viz[it]){

            dfst(it);
        }
    }
}

int main(){

    cin >> n >> m;

    in = n;

    while(m--){

        cin >> x >> y;

        g[x].push_back(y);
        gt[y].push_back(x);
    }

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

        if(!viz[i]) dfs(i);
    }

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

        if(viz[i]){

            aux.clear();

            dfst(i);

            ctc.push_back(aux);
        }
    }

    cout << ctc.size() << '\n';

    for(auto it : ctc){

        for(auto i : it){

            cout << i << ' ';
        }

        cout << '\n';
    }

    return 0;
}