Cod sursa(job #943060)

Utilizator BeniaminMarcu Beniamin Beniamin Data 24 aprilie 2013 09:48:52
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.58 kb
#include<fstream>
#include<vector>
#include<stack>
#define lmax 110000

using namespace std;

vector <int> vecin[lmax], vecin_2[lmax], v[lmax];
int k, n;
int parcurs1[lmax];
int parcurs2[lmax];
stack<int> s;

ofstream fout("ctc.out");

void df1(int nod)
{
    parcurs1[nod] = 1;
    vector<int> :: iterator it;
    for(it = vecin[nod].begin(); it < vecin[nod].end(); it++)
    {
        if(parcurs1[vecin[nod][*it]] == 0)
            df1(vecin[nod][*it]);
    }
    s.push(nod);
}
void df2(int nod)
{
    v[k].push_back(nod);
    parcurs2[nod] = 1;
    vector<int> :: iterator it;
    for(it = vecin_2[nod].begin(); it < vecin_2[nod].end(); it++)
    {
        if(parcurs2[vecin_2[nod][*it]] == 0)
            df2(vecin_2[nod][*it]);
    }
}
void kosaraju()
{
    for(int i = 1; i <= n; i++)
        if(parcurs1[i] == 0)
            df1(i);

    while(!s.empty())
    {
        if(parcurs2[s.top()] == 0)
            {
                k++;
                df2(s.top());
            }
       s.pop();
    }
}
void citire()
{
    ifstream fin("ctc.in");
    int m, x, y, i;
    fin >> n >> m;
    for(i = 1; i <= m; i++)
    {
        fin >> x >> y;
        vecin[x].push_back(y);
        vecin_2[y].push_back(x);
    }
}
void afisare()
{
    vector<int> :: iterator it;
    fout << k << "\n";
    for(int i = 1; i <= k; i++)
    {
        for(it = v[i].begin(); it < v[i].end(); it++)
            fout << v[i][*it] << " ";
            fout << "\n";
    }
}
int main()
{
    citire();
    kosaraju();
    afisare();

    return 0;
}