Cod sursa(job #1165071)

Utilizator cosmin.pascaruPascaru Cosmin cosmin.pascaru Data 2 aprilie 2014 14:04:48
Problema Componente tare conexe Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 1.32 kb
#include <fstream>
#include <bitset>
#include <vector>

#define NMAX 100000
#define pb push_back
using namespace std;

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

int n, lg, nrTC;
vector <int> G[NMAX], GT[NMAX], sol[NMAX];
bitset <NMAX> viz;
int tsort[NMAX];

void citire()
{
    int m, x, y;
    fin >> n >> m;
    while (m--)
    {
        fin >> x >> y;
        G[x].pb(y);
        GT[y].pb(x);
    }
}
void DF (int x)
{
    viz[x] = 1;
    for (vector <int> :: iterator it = G[x].begin(); it != G[x].end(); ++it)
        if (!viz[*it]) DF(*it);
    tsort[++lg] = x;
}
void DFT (int x)
{
    viz[x] = 1;
    sol[nrTC].pb(x);
    for (vector <int> :: iterator it = GT[x].begin(); it != GT[x].end(); ++it)
        if (!viz[*it]) DFT(*it);
}
void ctc_tarjan()
{
    for (int i = 1; i <= n; ++i)
        if (!viz[i]) DF(i);
    viz.reset();
    for (int i = lg; i > 0; --i)
        if (!viz[tsort[i]])
        {
            ++nrTC;
            DFT(tsort[i]);
        }
}
void afisare()
{
    fout << nrTC << '\n';
    for (int i = 1; i <= nrTC; ++i)
    {
        for (vector <int> :: iterator it = sol[i].begin(); it != sol[i].end(); ++it)
            fout << *it << " ";
        fout << '\n';
    }
}
int main()
{
    citire();
    ctc_tarjan();
    afisare();
    return 0;
}