Cod sursa(job #3369952)

Utilizator MariaB144Maria Belceanu MariaB144 Data 22 octombrie 2026 17:33:18
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.08 kb
#include <iostream>
#include <fstream>
#include <vector>


using namespace std;

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


vector<int> h[100005];
vector<int> g[100005];
vector<int> scc[100005];//stronly conn comp

int n, m ,nrc, 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);
    }
    scc[nrc].push_back(n);

}

void SCC(){
    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){
            nrc++; DFS2(st[i]);
        }
    }
}

void Afisare(){
    fout<<nrc<< "\n";
    for(int i =1 ; i<=nrc ; i++){
        for(int j : scc[i]){
            fout<<j<< " ";
        }
        fout<<"\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);
    }
    SCC();
    Afisare();
    return 0;
}