Cod sursa(job #1095413)

Utilizator Athena99Anghel Anca Athena99 Data 30 ianuarie 2014 21:40:19
Problema Componente tare conexe Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.35 kb
#include <fstream>
#include <stack>
#include <vector>

using namespace std;

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

const int nmax= 100000;

int k, ksol;
int index[nmax+1], lp[nmax+1];
bool u[nmax+1];
stack <int> s;
vector <int> v[nmax+1], sol[nmax+1];

void dfs( int node ) {
    ++k;
    index[node]= lp[node]= k;
    s.push(node), u[node]= 1;

    for ( vector <int>::iterator it= v[node].begin(); it!=v[node].end(); ++it ) {
        if ( index[*it]==0 ) {
            dfs(*it);
            if ( lp[*it]<lp[node] ) {
                lp[node]= lp[*it];
            }
        } else if ( u[*it]==1 && lp[*it]<lp[node] ) {
            lp[node]= lp[*it];
        }
    }

    if ( index[node]==lp[node] ) {
        ++ksol;
        while ( s.top()!=node ) {
            sol[ksol].push_back(s.top());
            s.pop();
        }
        sol[ksol].push_back(s.top());
        s.pop();
    }
}

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

    for ( int i= 1; i<=n; ++i ) {
        if ( index[i]==0 ) {
            dfs(i);
        }
    }
    
    fout<<ksol<<"\n";
    for ( int i= 1; i<=ksol; ++i ) {
        for ( vector <int>::iterator it= sol[i].begin(); it!=sol[i].end(); ++it ) {
            fout<<*it<<" ";
        }
        fout<<"\n";
      }

    return 0;
}