Cod sursa(job #1752937)

Utilizator florinpocolPocol Florin florinpocol Data 5 septembrie 2016 15:51:22
Problema Parcurgere DFS - componente conexe Scor 10
Compilator c Status done
Runda Arhiva educationala Marime 2.81 kb
#include <stdio.h>
#include <stdlib.h>

typedef struct lista
{
    int nod;
    struct lista *next;
} *lista;

typedef struct stiva
{
    int inf;
    struct stiva *next;
} *stiva;
stiva prim;
lista l[100105];
int test,count;

int ok[100105]; //e initializat cu 0
int n,m;

void citire()
{
    freopen("dfs.in","r",stdin);
    freopen("dfs.out","w",stdout);
    scanf("%d %d",&n,&m);

    int i,x,y;
    lista nou;
    for (i=1; i<=m; i++)
    {
        scanf("%d %d",&x,&y);
        nou=calloc(1,sizeof(lista));
        nou->nod=y;
        nou->next=l[x];
        l[x]=nou;

        nou=calloc(1,sizeof(lista));
        nou->nod=x;
        nou->next=l[y];
        l[y]=nou;

    }

}

void afisare()
{
    int i;
    for (i=1; i<=n; i++)
    {
        printf("%d :  ",i);
        lista p;
        p=l[i];
        while (p)
        {
            printf("%d, ",p->nod);
            p=p->next;
        }
        printf("\n");
    }
}


pune_in_stiva(int nod)
{
    stiva nou;
    nou=calloc(1,sizeof(stiva));
    nou->inf=nod;


    nou->next=prim;
    prim=nou;
}



scoate_din_stiva()
{
    stiva aux;

    aux=prim;
    prim=prim->next;

    free(aux);
}

void afisare_stiva()
{
    stiva aux;
    aux=prim;

    while (aux)
    {
        printf("%d ",aux->inf);
        aux=aux->next;
    }
    printf("\n");
}


void dfs(int nod)
{
    lista p;
    while (prim!=NULL)
    {
        p=l[nod];
        while (p)
        {


            if (ok[p->nod]==0)
               {
                   ok[p->nod]=1;
                   pune_in_stiva(p->nod);
                   dfs(p->nod);
               }

            p=p->next;

         }
        ok[nod]=2;
                                     /*
                                     afisare_stiva();
                                     printf("hai :");
                                     afisare_rezultat();
                                     printf("\n");
                                     */

         if (ok[test]!=2)
             {
                 scoate_din_stiva();
             }
    }
}

void afisare_rezultat()
{
    int i;
    for (i=1; i<=n; i++)
        {
            printf("%d ",ok[i]);
        }
}


void rezolvare()
{
    int i=1;

    while (i<=n)
    {
        if (l[i]!=NULL)
            {
                test=i;
                ok[test]=1;
                pune_in_stiva(test);
                dfs(test);
            }
            else
            {
                ok[i]=2;
            }
        //afisare_rezultat();
        //printf("\n");
        count++;
        while (ok[i])
            i++;
    }
}


int main()
{
    citire();
    //afisare();
    count=0;
    rezolvare();
    printf("%d",count);
    return 0;
}