Cod sursa(job #1212580)

Utilizator mariusn01Marius Nicoli mariusn01 Data 25 iulie 2014 11:36:57
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.23 kb
#include <fstream>
#include <vector>
#include <bitset>
#include <stack>
#define DIM 100010
using namespace std;

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

vector<int> L[DIM], R[DIM];
bitset<DIM> v, IS;
stack<int> s;

int low[DIM], niv[DIM];

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

void dfs(int nod) {
    g++;
    niv[nod] = g;
    low[nod] = g;
    s.push(nod);
    IS[nod] = 1;
    v[nod] = 1;

    for (int i = 0; i<L[nod].size(); i++) {
        int x = L[nod][i];
        if (!v[x]) {
            dfs(x);
            low[nod] = min(low[nod], low[x]);
        } else
            if (IS[x])
                low[nod] = min(low[nod], low[x]);
    }
    int x;
    if (low[nod] == niv[nod]) {
        ctc++;
        do {
            x = s.top();
            s.pop();
            IS[x] = 0;
            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])
            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;
}