Cod sursa(job #1234480)

Utilizator AeroHHorea Stefan AeroH Data 27 septembrie 2014 14:31:38
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.2 kb
#include <fstream>
#include <vector>
#define pb push_back
#include <algorithm>
#define NMAX 100001
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");

int i,j,k,x,y,viz[NMAX],ans[NMAX],nr,m,n;

vector<int> v[NMAX],w[NMAX],rasp[NMAX];

void df1(int nod)
    {
        viz[nod]=1;
        int i=0;
        for (i=0;i<v[nod].size();++i)
            if (!viz[v[nod][i]])
                df1(v[nod][i]);
        ans[++ans[0]]=nod;
    }

void df2(int nod)
    {
        viz[nod]=1;
        rasp[nr].pb(nod);
        int i=0;
        for (i=0;i<w[nod].size();++i)
            if (!viz[w[nod][i]])
                df2(w[nod][i]);
    }

int main()
{
    f>>n>>m;
    for (i=1;i<=m;++i)
        {
            f>>x>>y;
            v[x].pb(y);
            w[y].pb(x);
        }
    for (i=1;i<=n;++i)
        if (!viz[i])df1(i);

    for (i=1;i<=n;viz[i]=0,++i);

    for (i=n;i>=1;--i)
        if (!viz[ans[i]])++nr,df2(ans[i]);

    g<<nr<<'\n';

    for (i=1;i<=nr;++i)
        {
            sort(rasp[i].begin(),rasp[i].end());
            for (j=0;j<rasp[i].size();++j)
                g<<rasp[i][j]<<" ";
            g<<'\n';
        }
    return 0;
}