Cod sursa(job #287231)

Utilizator sigridMaria Stanciu sigrid Data 24 martie 2009 17:24:12
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.87 kb
#include<stdio.h>
#define dim 100//010

struct lista
{
      int varf;
      
      lista *urm; 
} *v[dim], *ultim[dim], *aux;

int N, M, cont;

int viz[dim], c[dim];

void adauga(int x, int y)
{
     if(v[x] == 0)
     {
             v[x] = new lista;
             
             v[x]->varf = y;
             v[x]->urm = 0;
             
             ultim[x] = v[x];
     }
     else
     {
         aux = new lista;
         
         aux->varf = y;
         aux->urm = 0;
         
         ultim[x]->urm = aux;
         
         ultim[x] = ultim[x]->urm;         
     }
}

int main()
{
    int i, x, y, ok, prim, ultim;
    
    freopen("dfs.in", "r", stdin);
    freopen("dfs.out", "w", stdout);
    
    scanf("%d %d", &N, &M);
    
    for(i = 1; i <= M; i++)
    {
          scanf("%d %d", &x, &y);
          
          adauga(x, y);
          adauga(y, x); 
    }
    
    for(i = 1; i <= N; i++)
          if( viz[i] == 0 )
          {
               cont++;
               
               c[0] = i;
               viz[i] = 1;
               prim = ultim = 0;
               
               while( prim <= ultim )
               {
                      x = c[prim];
                      prim++;
                      
                      ok = 1;
                      
                      while( ok )
                      {
			                 if( viz[v[x]->varf] == 0 )
                             {
				                 viz[v[x]->varf] = 1;

				                 ultim++;
				                 c[ultim] = v[x]->varf;
                             }

			                 if( v[x]->urm == 0 )
				                 ok = 0;

                             v[x] = v[x]->urm;
                     }
               }
               
          }
          
    printf("%d \n", cont);
    
    return 0;
    
}