Cod sursa(job #2440894)

Utilizator Stefan3002Stefan Stefan3002 Data 19 iulie 2019 15:38:35
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.35 kb
#include <iostream>
#include <vector>
#include <fstream>
#include <stack>
using namespace std;
ifstream intrare("ctc.in");
ofstream iesire("ctc.out");
const int NMAX=105;

int i,j,n,m,sol;
int vizitat[NMAX];

vector < int >graf[NMAX],graf2[NMAX],solutie[NMAX];
stack <int >s;


int DFS(int nodStart){

for(size_t i=0;i<graf[nodStart].size();i++){
    int vecin=graf[nodStart][i];
    if(!vizitat[vecin]){
        vizitat[vecin]=1;
        DFS(vecin);
    }
}
s.push(nodStart);


}
int DFS2(int nodStart){
vizitat[nodStart]=2;
solutie[sol].push_back(nodStart);
for(size_t i=0;i<graf2[nodStart].size();i++){
    int vecin=graf2[nodStart][i];
    if(vizitat[vecin]==1){
        vizitat[vecin]=2;
        DFS2(vecin);


    }



}




}







int main()
{
    intrare>>n>>m;
    for(i=1;i<=m;i++)
    {int o,l;
        intrare>>o>>l;
        graf[o].push_back(l);
        graf2[l].push_back(o);
    }

    for(i=1;i<=n;i++)
        if(!vizitat[i])
        DFS(i);

    while(!s.empty()){
        int nod=s.top();
        if(vizitat[nod]==1){
                sol++;
        DFS2(nod);

        }
        s.pop();
    }
    iesire<<sol;
    for(j=0;j<=sol;j++){
            iesire<<endl;
    for(size_t i=0;i<solutie[j].size();i++)
       iesire <<solutie[j][i]<<" ";

    }



    return 0;
}