Cod sursa(job #1039087)

Utilizator dumitrualexAlex Dumitru dumitrualex Data 22 noiembrie 2013 15:11:34
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.91 kb
#include <fstream>
#include <vector>
#include <set>
#include <queue>
#define FORV(it, C) for( vector<int>::iterator it = C.begin(); it != C.end(); it++)
#define FORRV(it, C) for ( vector<int>::reverse_iterator it = C.rbegin(); it != C.rend(); it++)
#define FORS(it, C) for( set<int>::iterator it = C.begin(); it != C.end(); it++)
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define nmax 100000+5
using namespace std;

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

vector<int> graf[nmax];
vector<int> grafTranspus[nmax];
vector<int> postOrdine;
vector<set<int> > componente;
queue<int> coada;
bool util[nmax];
int n, m;

void citire()
{
    int x, y;
    fin >> n >> m;
    FOR(i, 1, m)
    {
        fin >> x >> y;
        graf[x].push_back(y);
        grafTranspus[y].push_back(x);
    }
}

void dfsPostOrdine(int vf)
{
    util[vf] = true;
    FORV(it, graf[vf])
        if (!util[*it])
            dfsPostOrdine(*it);
    postOrdine.push_back(vf);
}

void bfsTranspus(int vf)
{
    int curent;
    set<int> componenta;
    util[vf] = false;
    coada.push(vf);

    while (!coada.empty())
    {
        curent = coada.front();
        coada.pop();

        componenta.insert(curent);

        FORV(it, grafTranspus[curent])
            if (util[*it])
            {
                util[*it] = false;
                coada.push(*it);
            }
    }
    componente.push_back(componenta);
}

void rezolvare()
{
    FOR(i, 1, n)
        if (!util[i])
            dfsPostOrdine(i);
    FORRV(it, postOrdine)
        if (util[*it])
            bfsTranspus(*it);
}

void afisare()
{
    fout << componente.size() << '\n';
    for (int i = 0; i < componente.size(); i++)
    {
        FORS(jt, componente[i])
            fout << *jt << ' ';
        fout << '\n';
    }
}

int main()
{
    citire();
    rezolvare();
    afisare();
    return 0;
}