Cod sursa(job #856107)

Utilizator Aida_SilviaStrimbeanu Aida Silvia Aida_Silvia Data 15 ianuarie 2013 22:28:04
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.21 kb
#include <cstdio>
#include <vector>

using namespace std;
const int nmax=100073;

vector <int> g[nmax], gt[nmax],cm[nmax];

int c,postviz[nmax],viz[nmax],ctc,n,m;

void df(int nod)
{
    unsigned int i;
    viz[nod]=1;

    for(i=0;i<g[nod].size();i++)
            if (!viz[g[nod][i]])
                df(g[nod][i]);
    c++;
    postviz[c]=nod;

}

void dft(int nod)
{
    unsigned int i;

    viz[nod]=0;
    cm[ctc].push_back(nod);

    for (i=0;i<gt[nod].size();i++)
        if (viz[gt[nod][i]])
            dft(gt[nod][i]);
}

int main()
{
    freopen("ctc.in","r",stdin);
    freopen("ctc.out","w",stdout);

    int i,x,y;

    scanf("%d%d",&n,&m);

    for ( i=1;i<=m;i++)
        {
            scanf("%d%d",&x,&y);
            g[x].push_back(y);
            gt[y].push_back(x);

        }

    for (i=1;i<=n;i++)
        if (!viz[i])
           df(i);

    for (i=n;i>=1;i--)
     if (viz[postviz[i]])
     {
         ctc++;
         dft(postviz[i]);
     }

     printf("%d\n",ctc);

     for (i=1;i<=ctc;i++)
     {
         for (unsigned int j=0;j<cm[i].size();j++)
            printf("%d ",cm[i][j]);
         printf("\n");
     }


    return 0;
}