Cod sursa(job #1461127)

Utilizator CollermanAndrei Amariei Collerman Data 14 iulie 2015 19:53:55
Problema Componente tare conexe Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.49 kb
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ofstream fout("ctc.out");
ifstream fin("ctc.in");
const int NMAX = 200005;

int n, m, idx, nr;
int lowlink[NMAX], index[NMAX];
bool onStack[NMAX], mark[NMAX];
vector<int> v[NMAX], sol[NMAX];
stack<int> s;

void citire()
{
    int x, y;

    fin >> n >> m;
    for(int i=1; i<=m; i++) {
        fin >> x >> y;
        v[x].push_back(y);
    }
}

void afis()
{
    fout << nr << '\n';
    for(int i=1; i<=nr; i++) {
        for(vector<int>::iterator it=sol[i].begin(); it<sol[i].end(); it++)
            fout << *it << ' ';
        fout << '\n';
    }
}

void strong_connect(int nod)
{
    mark[nod] = true;

    onStack[nod] = true;
    s.push(nod);

    idx++;
    lowlink[nod] = idx;
    index[nod] = idx;

    for(int i=0; i<v[nod].size(); i++) {
        if(!mark[v[nod][i]]) {
            strong_connect(v[nod][i]);
            lowlink[nod] = min(lowlink[nod], lowlink[v[nod][i]]);
        }
        else if(onStack[nod]) {
            lowlink[nod] = min(lowlink[nod], index[v[nod][i]]);
        }
    }

    if(index[nod] == lowlink[nod]) {
        int aux;
        nr++;
        do{
            aux = s.top();
            s.pop();
            onStack[aux] = false;
            sol[nr].push_back(aux);
        }while(aux != nod);
    }
}

int main()
{
    citire();
    for(int i=1; i<=n; i++)
        if(!mark[i])
            strong_connect(i);
    afis();
    return 0;
}