Cod sursa(job #369220)

Utilizator bora_marianBora marian bora_marian Data 27 noiembrie 2009 16:10:10
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.99 kb
#include<fstream>
#include<iostream>
#include <cstdlib>
using namespace std;
struct nod{
    int info;
    nod *next;};
int n,v[100001];
nod  *a[100001];
void dfs(int k,int nrc);
void citire();
void dfs(int k,int nrc);

int main()
{
   int max=0,i,nrc;
   citire();
   nrc=0;
   for(i=1;i<=n;i++)
     if(v[i]==0)
     {
        dfs(i,++nrc);
     }
   ofstream fout("dfs.out");
      fout<<nrc;
 return 0;
} 
 void citire()
 {
   ifstream fin("dfs.in");
   int m;
   fin>>n>>m;
   for(int i=1;i<=n;i++)
     a[i]=NULL;
   for(;m;m--)
    {
     int i,j;
     fin>>i>>j;
     nod*p;
     p=new nod;
     p->info=j;
     p->next=a[i];
     a[i]=p;
     p=new nod;
     p->info=i;
     p->next=a[j];
     a[j]=p;
    }
} 
 void dfs(int k,int nrc)
 {
  nod *p = a[k];
  v[k] = nrc;
  while(p!=NULL)
   {
     if(v[p->info]==0)
     { 
           v[p->info]=nrc;
           dfs(p->info,nrc);
     }
     p=p->next;      
   }
}