Cod sursa(job #1592117)

Utilizator dianaorasanuDiana Orasanu dianaorasanu Data 7 februarie 2016 00:55:39
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.49 kb
#include <fstream>
#include <vector>

#define NMAX 100010

using namespace std;

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

void DFS(int x);
void DFSt(int x);

int n, m, i, j;
vector <int> unu, doi[NMAX], M[NMAX*2], T[NMAX*2];
int  elem, elem2, ctc, x, y;
vector <bool> v;

int main()
{
    fin >> n >> m;
    for(i = 1; i <= n; ++i)
        v.push_back(false);
    for(i = 1; i <= m; ++i)
    {
        fin >> x >> y;
        M[x].push_back(y);
        T[y].push_back(x);
    }
    for(i = 1; i <= n; ++i)
    {
        if(v[i] == false)
        {
            v[i] = true;
            DFS(i);
            //elem = 0;
        }
    }
    for(i = unu.size()-1; i >= 0; --i)
    {
        if(v[unu[i]] == true)
        {
            v[unu[i]] = false;
            ctc++;
            DFSt(unu[i]);
        }
    }
    fout << ctc << '\n';
    for(i = 1; i <= ctc; ++i)
    {
        for(j = doi[i].size()-1; j >= 0; --j)
            fout << doi[i][j] << ' ';
        fout << '\n';
    }
    return 0;
}

void DFS(int x)
{
    int i;
    for(i = 0; i < M[x].size(); ++i)
    {
        if(v[M[x][i]] == false)
        {
            v[M[x][i]] = true;
            DFS(M[x][i]);
        }
    }
    unu.push_back(x);
}

void DFSt(int x)
{
    int i;
    for(i = 0; i < T[x].size(); ++i)
    {
        if(v[T[x][i]] == true)
        {
            v[T[x][i]] = false;
            DFSt(T[x][i]);
        }
    }
    doi[ctc].push_back(x);
}