Cod sursa(job #1403783)

Utilizator dutzulBodnariuc Dan Alexandru dutzul Data 27 martie 2015 16:16:03
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.23 kb
//#include <iostream>
#include <fstream>
using namespace std;

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

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


vector<int> H[LE],res[LE];

int Tmin[LE],st[LE];
bool  fr[LE],viz[LE];
int k=0,nr_comp=0;

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

    int fp=k;
    Tmin[nod]=k;

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

    if (Tmin[nod]==fp)
    {
        ++nr_comp;
        for(i=fp; i<=k; ++i)
        {
          res[nr_comp].pb(st[i]);
          fr[st[i]]=false;
          }
        k=fp-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);

    g<<nr_comp<<'\n';

    for(i=1;i<=nr_comp;++i)
    {
       int N=res[i].size();
       for(int j=0;j<N;++j) g<<res[i][j]<<" ";
       g<<'\n';
    }


    return 0;
}