Cod sursa(job #1329322)

Utilizator dutzulBodnariuc Dan Alexandru dutzul Data 29 ianuarie 2015 13:24:31
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.17 kb
//#include <iostream>
#include <fstream>

#define LE 100666
#define pb push_back
#include <vector>

using namespace std;

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

vector<int> H[LE];
vector<int> result[LE];
int Timp[LE],st[LE];
bool viz[LE],fr[LE];
int K,nr_comp,tmps;

void dfs(int nod)
{
    int N=H[nod].size(),i;
    viz[nod]=true;

    Timp[nod]=++tmps;
    int timpi=Timp[nod];
    st[++K]=nod;
    int stp=K;
    fr[nod]=true;

    for(i=0; i<N; ++i)
    {
        int D=H[nod][i];

        if (viz[D]==false)
            dfs(D);

        if (fr[D])
            Timp[nod]=min(Timp[nod],Timp[D]);
    }


    if (Timp[nod]!=timpi) return;

    ++nr_comp;

    for(i=stp; i<=K; ++i)
    {
        result[nr_comp].pb(st[i]);
        fr[st[i]]=false;
    }

    K=stp-1;
}

int main()
{
    int n,m,i;

    f>>n>>m;

    for(i=1; i<=m; ++i)
    {
        int xx,yy;
        f>>xx>>yy;
        H[xx].pb(yy);
    }

    for(i=1; i<=n; ++i)
        if (viz[i]==false)
            dfs(i);


    cout<<nr_comp<<'\n';

    for(i=1; i<=nr_comp; ++i)
    {
        int j,N2=result[i].size();
        for(j=0; j<N2; ++j) cout<<result[i][j]<<" ";
        cout<<'\n';
    }

    return 0;
}