Cod sursa(job #1197175)

Utilizator azkabancont-vechi azkaban Data 10 iunie 2014 22:55:51
Problema Parcurgere DFS - componente conexe Scor 85
Compilator cpp Status done
Runda Arhiva educationala Marime 1.08 kb
#include <fstream>
#include <algorithm>
#include <cstring>
using namespace std;
ifstream cin("dfs.in");
ofstream cout("dfs.out");
typedef struct celula {
                        int nod;
                        celula *next;
                       }*lista;
                       
void add(int val, lista &p)
{
  lista r;
  r= new celula;
  r->nod=val;
  r->next=p;
  p=r;  
} 

void dfs ( int nod,int viz[],lista lda[] ) 
{
  viz[nod]=1;
  for (lista r=lda[nod];r;r=r->next) 
     if (viz[r->nod]==0) dfs(r->nod,viz,lda);  
}

int main()
{
  lista lda[100000];
  int viz[100000],i,n,m,a,b,nr;
  cin>>n>>m;
  memset(lda,0,sizeof(lda));
  memset(viz,0,sizeof(viz));
  for (i=1;i<=m;i++) {
                       cin>>a>>b;
                       add(a,lda[b]);
                       add(b,lda[a]);
                     }
  for (i=1;i<=n;i++) 
                      if ( viz[i]==0 ) {
                                         nr+=1;
                                         dfs(i,viz,lda);
                                        }
 cout<<nr;
 return 0;
}