Cod sursa(job #280363)

Utilizator silaghi_raulSzilagyi Raul Razvan silaghi_raul Data 13 martie 2009 12:39:45
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.19 kb
#include<stdio.h>
#include<string.h>
#define nmax 100001
// componente tare conexe
int n,m,
st[nmax], // stiva
ns,    // nivel stiva
viz[nmax], //  vizitate
cont;     // comp conexe

struct nod
{
    int drum;
    nod *urm;
} *l[nmax] , // graf normal
 *lt[nmax];  // graf transpus

void DF1(int);
void DF2(int);
void DF_afis(int);
void add(nod *&inc,int info)
{   // adauga un nod in lista vecinilor
    nod *p=new nod;
    p->drum=info;
    p->urm=inc;
    inc=p;
}

int main()
{
    int a,b;
    freopen("ctc.in","r",stdin);
    freopen("ctc.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;++i)
        {   // citim muchiile si le adaugam in cele 2 liste
            scanf("%d%d",&a,&b);
            add(l[a],b);
            add(lt[b],a);
        }

    for(int i=1;i<=n;++i)
        if (!viz[i]) // pentru fiecare nod nevizitat
            DF1(i); // parcurgem in adancime

    memset(viz,0,sizeof(viz)); // reinitializam Viz[]

    for(int i=n;i;--i) // pentru fiecare nod din stiva
        if (!viz[st[i]])// daca nu e vizitat
            {
                DF2(st[i]); // parcurgem pe graful transpus
                ++cont; // numaram nr de comp conexe
                //printf("\n");
            }
    printf("%d\n",cont); // afisam numaru de comp conexe

    memset(viz,0,sizeof(viz)); // reinitializam viz[]

    for(int i=n;i;--i)// pentru fiecare nod
        if (!viz[st[i]])// daca nu e vizitat
            {
                DF_afis(st[i]); // parcurgem in adancime si afisam nodurile
                printf("\n"); // din  componenta conexa curenta
            }
    return 0;
}

void DF1 (int x)
{
    nod *p=l[x];// parcurgere in adancime
    viz[x]=1;   // pe graf normal

    for(;p;p=p->urm)
        if (!viz[p->drum])
            DF1(p->drum);

    st[++ns]=x; // punem nodul in stiva in ordine inversa DF

}

void DF2(int x)
{
    nod *p=lt[x];
    viz[x]=1;
    //printf("%d ",x);
    for(;p;p=p->urm)
        if (!viz[p->drum])
            DF2(p->drum);
}

void DF_afis(int x)
{
    nod *p=lt[x];
    viz[x]=1;
    printf("%d ",x);
    for(;p;p=p->urm)
        if (!viz[p->drum])
            DF_afis(p->drum);
}