Cod sursa(job #2346491)

Utilizator corina_dimitriuDimitriu Corina corina_dimitriu Data 17 februarie 2019 19:09:36
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.61 kb
#include <fstream>
#include <vector>
#include <queue>
#define NMAX 100005

using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
void citire();
void afisare();
void DFSp(int nod);
void DFSm(int nod);
int N,M,cnt;
int viz[NMAX];
vector <int> g[NMAX],gt[NMAX],rez[NMAX];
vector <int> Q;
int main()
{
    int i,j;
    citire();
    for(i=1; i<=N; i++)
        if(!viz[i])
        {

            viz[i]=1;
            DFSp(i);
        }
    for(i=1; i<=N; i++)
        viz[i]=0;
        cnt =0;
    for(i=Q.size()-1; i>=0; i--)
        if(!viz[Q[i]])
        {
            cnt++;
            rez[cnt].push_back(Q[i]);
            viz[Q[i]]=1;
            DFSm(Q[i]);
        }
    afisare();
    return 0;
}
void citire()
{
    int i,ei,ef;
    fin>>N>>M;
    for(i=1; i<=M; i++)
    {
        fin>>ei>>ef;
        g[ei].push_back(ef);
        gt[ef].push_back(ei);
    }
}
void DFSp(int nod)
{
    vector <int>::iterator it;
    for(it=g[nod].begin(); it!=g[nod].end(); it++)
        if(!viz[*it])
        {
            viz[*it]=1;
            DFSp(*it);

        }
        Q.push_back(nod);

}
void DFSm(int nod)
{
    vector <int>::iterator it;
    for(it=gt[nod].begin(); it!=gt[nod].end(); it++)
        if(!viz[*it])
        {
            viz[*it]=1;
            DFSm(*it);
            rez[cnt].push_back(*it);
        }
}
void afisare()
{
    int i;
    fout<<cnt<<'\n';
    vector <int>::iterator it;
    for(i=1; i<=cnt; i++)
    {
        for(it=rez[i].begin(); it!=rez[i].end(); it++)
            fout<<*it<<' ';
        fout<<'\n';
    }
}