Cod sursa(job #1715709)

Utilizator killer301Ioan Andrei Nicolae killer301 Data 11 iunie 2016 13:38:45
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.96 kb
#include <stdio.h>

#define Nmax 200100

struct nod{
    int info;
    nod *next;
};

nod *p[Nmax];
nod *pt[Nmax];

int n,m,nr,viz[Nmax],postordine[Nmax],rev[Nmax],com;

void adauga(int j, int k)
{
    nod *elem=new nod;
    elem->info=k;
    elem->next=p[j];
    p[j]=elem;
}

void adaugat(int j, int k)
{
    nod *elem=new nod;
    elem->info=k;
    elem->next=pt[j];
    pt[j]=elem;
}

void DFS(int i)
{
    nod *current=p[i];
    viz[i]=1;
    while(current!=NULL)
        {
            if(viz[current->info]==0)
                DFS(current->info);
            current=current->next;
        }
    postordine[++nr]=i;
}

void DFST(int i)
{
    nod *current=pt[i];
    viz[i]=0;
//  printf("%d ",i);
    adauga(n+com,i);
    while(current!=NULL)
        {
            if(viz[current->info]!=0)
                DFST(current->info);
            current=current->next;
        }
}

void revizit(int i)
{
    nod *current=pt[i];
    rev[i]=1;
    while(current!=NULL)
        {
            if(rev[current->info]==0)
                revizit(current->info);
            current=current->next;
        }
}

void afis(int i)
{
    nod *current=p[i];
    while(current)
        {
            printf("%d ",current->info);
            current=current->next;
        }
}

int main()
{
    int i,x,y;
    freopen("ctc.in","r",stdin);
    freopen("ctc.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;++i)
        {
            scanf("%d%d",&x,&y);
            adauga(x,y);
            adaugat(y,x);
        }

    for(i=1;i<=n;++i)
        {
            if(viz[i]==0)
                DFS(i);
        }
    for(i=n;i>0;--i)
        if(viz[postordine[i]]!=0)
            {
                ++com;
                DFST(postordine[i]);
            }
    printf("%d\n",com);
    for(i=1;i<=com;++i,printf("\n"))
        for(nod *it=p[n+i];it;it=it->next)
            printf("%d ",it->info);
    return 0;
}