Cod sursa(job #2509501)

Utilizator Mirela_MagdalenaCatrina Mirela Mirela_Magdalena Data 14 decembrie 2019 11:56:58
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.27 kb
#define NMAX 100005
#include <fstream>
#include <stack>
#include <vector>
using namespace std;

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

int n, m, nr, nrC, nrviz;
int viz[NMAX];
vector<int> G[NMAX], Gt[NMAX];
vector<int> afis[NMAX];
stack<int> parc;

void read()
{
    int x, y;

    f>>n>>m;
    for(int i=1; i<=m; ++i)
    {
        f>>x>>y;
        G[x].push_back(y);
        Gt[y].push_back(x);
    }
}


void DFS(int nod)
{
    nrviz++;
    viz[nod] = -1;
    for(auto &v:G[nod])
        if(viz[v] == 0)
            DFS(v);
    parc.push(nod);
}

void DFSt(int nod, int nr)
{
    viz[nod] = nr;
    for(auto &v:Gt[nod])
        if(viz[v] <= 0)
            DFSt(v, nr);
    afis[nr].push_back(nod);
}

void afisare()
{
    g<<nr<<"\n";
    for(int i=1; i<=nr; ++i)
    {
        for(auto &v:afis[i])
            g<<v<<" ";
        g<<'\n';
    }
}




int main()
{
    read();
    while(nrviz < n)
    {
        for(int i=1; i<=n; ++i)
            if(viz[i] == 0)
                DFS(i);
    }
    while(!parc.empty())
    {
        int vf = parc.top();
        if(viz[vf] > 0)
            parc.pop();
        else{
            nr++;
            DFSt(vf, nr);
        }
    }
    afisare();


    return 0;
}