Cod sursa(job #1047095)

Utilizator dutzulBodnariuc Dan Alexandru dutzul Data 3 decembrie 2013 21:55:31
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.19 kb
//#include <iostream>
#include <fstream>
using namespace std;

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

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

vector<int> H[LE],result[LE];
int i,k,nrc,st[LE];
bool fr[LE],viz[LE];
int n,m,hmin[LE],T;

void dfs(int nod)
{
    int N=H[nod].size(),i;
    viz[nod]=true;
    st[++k]=nod;
    fr[nod]=true;
    hmin[nod]=++T;
    int lev=T,stk=k;

    for(i=0; i<N; ++i)
    {
        int D=H[nod][i];
        if (viz[H[nod][i]]==false)  dfs(D);
        if (fr[D]) hmin[nod]=min(hmin[nod],hmin[D]);
     }

    if (hmin[nod]==lev)
    {
        for(i=stk,++nrc; i<=k; ++i)
        {
            result[nrc].pb(st[i]);
            fr[st[i]]=false;
        }
        k=stk-1;
    }
}

int main()
{
    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)
        {
            k=0;
            dfs(i);
        }

    cout<<nrc<<'\n';

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


    f.close();
    g.close();
    return 0;
}