Cod sursa(job #3251816)

Utilizator Bogdan345Marius Mihalache Bogdan345 Data 27 octombrie 2024 09:38:18
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.71 kb
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream cin("ctc.in");
ofstream cout("ctc.out");
vector<vector<int>>gr,gr_t;
vector<int>folosit,rasp;
stack<int>s;
int nr_com_conx=0;
void DFS(int nod){
    for(int i=0;i<gr[nod].size();i++){
        if(folosit[gr[nod][i]]==-1){
            folosit[gr[nod][i]]=1;
            DFS(gr[nod][i]);
        }
    }//vizitez mai intai toti vecini sai,de-abia dupa
    //pot sa spun ca am finalizat nodul respectiv
    s.push(nod);
}

void DFS1(int nod){
   rasp.push_back(nod);
    for(int i=0;i<gr_t[nod].size();i++){
        if(folosit[gr_t[nod][i]]==-1){
            folosit[gr_t[nod][i]]=1;
            DFS1(gr_t[nod][i]);
        }
    }
}

int n,m,nod1,nod2;
int main(){
    cin>>n>>m;
    gr.resize(n+1);
    gr_t.resize(n+1);
    folosit.resize(n+1,-1);
    for(int i=1;i<=m;i++){
        cin>>nod1>>nod2;
        gr[nod1].push_back(nod2);
        gr_t[nod2].push_back(nod1);
    }
    for(int i=1;i<=n;i++){
        if(folosit[i]==-1){
            folosit[i]=1;
            DFS(i);
        }
    }
    for(int i=1;i<=n;i++){
        folosit[i]=-1;
    }
    
    int nod_curent;
    while(!s.empty()){
        nod_curent=s.top();
        s.pop();
        if(folosit[nod_curent]==-1){
            nr_com_conx+=1;
            folosit[nod_curent]=1;
            DFS1(nod_curent);
            rasp.push_back(-1);
            
        }
    }
    cout<<nr_com_conx<<'\n';
    for(int i=0;i<rasp.size();i++){
        if(rasp[i]==-1){
            cout<<'\n';
        }else{
            cout<<rasp[i]<<" ";
        }
    }
   
    gr.clear();
    gr_t.clear();
    folosit.clear();
    rasp.clear();
}