Cod sursa(job #1211024)

Utilizator mariusn01Marius Nicoli mariusn01 Data 21 iulie 2014 21:32:22
Problema Componente tare conexe Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.07 kb
#include <fstream>
#include <vector>
#include <stack>

#define DIM 100010

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

vector<int> L[DIM];
vector<int> R[DIM];
stack<int> S;

int v[DIM], niv[DIM], low[DIM];

int n, m, i, j, x, y, ctc, g;

void dfs(int nod) {
    S.push(nod);
    g++;
    niv[nod] = g;
    low[nod] = g;
    v[nod] = 1;
    for (int i=0;i<L[nod].size(); i++) {
        if (v[ L[nod][i] ] == 0)
            dfs(L[nod][i]);
        low[nod] = min(low[nod], low[L[nod][i]]);
    }

    if (low[nod] == niv[nod]) {
        ctc++;
        do {
            x = S.top();
            S.pop();
            R[ctc].push_back(x);
        } while (x!=nod);
    }

}

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

    for (i=1;i<=n;i++)
        if (v[i] == 0)
            dfs(i);

    fout<<ctc<<"\n";
    for (i=1;i<=ctc;i++) {
        for (j=0;j<R[i].size();j++)
            fout<<R[i][j]<<" ";
        fout<<"\n";
    }

    return 0;
}