Cod sursa(job #943065)

Utilizator BeniaminMarcu Beniamin Beniamin Data 24 aprilie 2013 10:31:29
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.44 kb
#include <fstream>
#include <vector>
#include <stack>

#define Nmax 100005
using namespace std;

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

int n, m;
int viz[Nmax], k;
vector <int> vecin1[Nmax], vecin2[Nmax], sol[Nmax];
stack <int> s;

void citire()
{
    int i, x, y;
    fin >> n >> m;
    for(i = 1; i <= m; ++i)
    {
        fin >> x >> y;
        vecin1[x].push_back(y);
        vecin2[y].push_back(x);
    }
}
void df1(int nod)
{
    vector <int> ::iterator it;
    viz[nod] = 1;

    for(it = vecin1[nod].begin(); it != vecin1[nod].end(); ++it)
        if(viz[*it] == 0)
            df1(*it);

   s.push(nod);
}
void df2(int nod)
{
    vector <int> ::iterator it;
    viz[nod] = 0;
    sol[k].push_back(nod);
    for(it = vecin2[nod].begin(); it != vecin2[nod].end(); ++it)
        if(viz[*it] == 1)
            df2(*it);
}
void kosaraju()
{
    int i;
    for(i = 1; i <= n; ++i)
        if(viz[i] == 0)
            df1(i);

    while(!s.empty())
    {
        if(viz[s.top()] == 1)
        {
            ++k;
            df2(s.top());
        }
        s.pop();
    }
}
void afisare()
{
    vector <int> ::iterator it;
    fout << k << '\n';

    for(int i = 1; i <= k; ++i)
    {
        for(it = sol[i].begin(); it != sol[i].end(); ++it)
            fout << *it << " ";
        fout << '\n';
    }
}
int main()
{
    citire();
    kosaraju();
    afisare();

    return 0;
}