Cod sursa(job #1213372)

Utilizator iordache.bogdanIordache Ioan-Bogdan iordache.bogdan Data 27 iulie 2014 22:54:41
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.23 kb
#include <fstream>
#include <vector>
#include <stack>
#define DIMN 100005

using namespace std;

ifstream f("ctc.in");
ofstream g("ctc.out");

vector<int> L[DIMN], Rez[DIMN];

int Niv[DIMN], Low[DIMN];

int m, n, ctc = 0, nivel = 0, x, y;

stack<int> s;

void DFS (int nod) {
    Niv[nod] = Low[nod] = ++nivel;
    s.push(nod);
    for (vector<int>::iterator it=L[nod].begin(); it!=L[nod].end(); ++it) {
        if (Niv[*it] == 0)
            DFS (*it);
        if (Niv[*it] > 0)
            Low[nod] = min(Low[nod], Low[*it]);
    }
    if (Niv[nod] == Low[nod]) {
        ++ctc;
        while (s.top() != nod) {
            Rez[ctc].push_back(s.top());
            Niv[s.top()] *= -1;
            s.pop();

        }
        Rez[ctc].push_back(s.top());
        Niv[s.top()] *= -1;
        s.pop();
    }
}

int main () {
    f >> n >> m;
    for (int i=1; i<=m; ++i) {
        f >> x >> y;
        L[x].push_back(y);
    }
    for (int i=1; i<=n; ++i)
        if (Niv[i] == 0)
            DFS (i);
    g << ctc << "\n";
    for (int i=1; i<=ctc; ++i) {
        for (vector<int>::iterator it=Rez[i].begin(); it!=Rez[i].end(); ++it)
            g << *it << " ";
        g << "\n";
    }
    return 0;
}