Cod sursa(job #3230007)

Utilizator pierdcasaPislariu Mario pierdcasa Data 18 mai 2024 18:30:05
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.45 kb
#include <bits/stdc++.h>
#define  Nmax 100005

using namespace std;

ifstream f("ctc.in");
ofstream g("ctc.out");

vector <int> G[Nmax],GT[Nmax],result[Nmax];
stack <int> S;

int N,M,NrCTC;
int beenThere[Nmax];

void Read()
{
    f>>N>>M;
    for(int i=1;i<=M;++i)
    {
        int x,y;
        f>>x>>y;
        G[x].push_back(y);
        GT[y].push_back(x);
    }
}


void DFS(int Nod)
{
    beenThere[Nod]=1;
    //Zona1
    for(unsigned int i=1;i<G[Nod].size();i++)
    {   //Zona 2
        int Vecin=G[Nod][i];
        if(!beenThere[Vecin])
            DFS(Vecin);
        //Zona 3
    }
    S.push(Nod);
    //Zona 4

}
void DFS_T(int Nod)
{
    beenThere[Nod]=2;
    result[NrCTC].push_back(Nod);

    for(unsigned int i=0;i<GT[Nod].size();i++)
        {int Vecin=GT[Nod][i];
         if(beenThere[Vecin]==1)
            DFS_T(Vecin);}

}
void Solve()
{
    for(int i=1;i<=N;++i)
    {
        if(!beenThere[i])
            DFS(i);
    }
    while(!S.empty())
    {
        int Nod=S.top();
        g<<Nod<<" ";
        if(beenThere[Nod]==1)
        {
            NrCTC++;
            DFS_T(Nod);
        }
        S.pop();
    }
}

void Print(){
  g<<NrCTC<<"\n";
  for(int i=1;i<=NrCTC;++i)
    {for(unsigned int j=0;j<result[i].size();j++)
     g<<result[i][j]<<" ";
    g<<"\n";}
}
int main()
{
    Read();
    Solve();
    Print();
    f.close();
    g.close();

    return 0;
}