Cod sursa(job #3369953)

Utilizator ericneaguEric Neagu ericneagu Data 22 octombrie 2026 17:40:40
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.99 kb
#include <iostream>
#include <fstream>
#include <vector>


using namespace std;

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


vector<int> h[100005];
vector<int> g[100005];
vector<int> tc[100005];

int n, m ,nr;
int st[100003], viz[100002], top;

void DFS(int nod) {
    viz[nod]=1;
    for(int i : h[nod]){
        if (viz[i] == 0)
            DFS(i);
    }
    st[++top] = nod;
}

void DFS2(int n){
    viz[n] = 0;
    for (int i : g[n]){
        if(viz[i]==1)
        DFS2(i);
    }
    tc[nr].push_back(n);

}

int main(){
    fin>>n>>m;
    for(int i =1 ; i<=m ; i++){
        int x,y;
        fin>>x>>y;
        h[x].push_back(y);
        g[y].push_back(x);
    }
    for ( int i =1 ; i <= n ; i++)
        if(viz[i]==0)
            DFS(i);
    for(int i=n ; i >0; i--){
        if(viz[st[i]]==1){
            nr++; DFS2(st[i]);
        }
    }
    gout<<nr<< "\n";
    for(int i =1 ; i<=nr ; i++){
        for(int j : tc[i]){
            gout<<j<< " ";
        }
        gout<<"\n";
    }

    return 0;
}