Cod sursa(job #2168560)

Utilizator danutmafteiMaftei Danut danutmaftei Data 14 martie 2018 11:31:15
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.35 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#define Nmax 100005

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


vector<int>lista[Nmax];
vector<int>listaT[Nmax];
priority_queue< int, vector<int>,greater<int> >raspuns[Nmax];

int nrc,nr;
bool viz[Nmax];
int postordine[Nmax];
int n,m;

void citire()
{
    int x,y;

    fin>>n>>m;

    while(m--)
    {
        fin>>x>>y;

        lista[x].push_back(y);
        listaT[y].push_back(x);
    }

    fin.close();
}


void DFS(int nod)
{
    viz[nod]=true;

    for(size_t i=0;i<lista[nod].size();++i)
        if(!viz[lista[nod][i]])
          DFS(lista[nod][i]);
    postordine[++nr]=nod;
}


void DFST(int nod)
{
    viz[nod]=false;
    raspuns[nrc].push(nod);

    for(size_t i=0;i<listaT[nod].size();++i)
        if(viz[listaT[nod][i]])
        DFST(listaT[nod][i]);
}
int main()
{
    citire();

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

    for(int i=n;i>=1;--i)
        if(viz[postordine[i]])
    { nrc++;
        DFST(postordine[i]);
    }

    fout<<nrc<<"\n";

    for(int i=1;i<=nrc;++i)
      {
          while(!raspuns[i].empty())
            {fout<<raspuns[i].top()<<" ";
            raspuns[i].pop();

            }
          fout<<"\n";
      }
    return 0;
}