Cod sursa(job #1197318)

Utilizator DjokValeriu Motroi Djok Data 11 iunie 2014 17:40:56
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.72 kb
#include<fstream>
#include<algorithm>
using namespace std;

typedef struct lnod {
     int info;
     lnod *next;
}*nod; 

int i,n,m,x,y,rs=0;
bool viz[100005];
nod lda[100005];

void add(int x,nod &y)
{
  nod p=new lnod;
  p->info=x;
  p->next=y;
  y=p;
}

void dfs(int x)
{
  nod p=new lnod;
  p=lda[x];
  viz[x]=1;
  for(p=p;p;p=p->next) 
  if(viz[p->info]==0) dfs(p->info);    
}

int main()
{
   ifstream cin("dfs.in");
   ofstream cout("dfs.out"); 
   
   cin>>n>>m;
   
   while(m--)
   {
     cin>>x>>y;
     add(x,lda[y]);
     add(y,lda[x]);                     
   }
   
   for(i=1;i<=n;++i)
   if(viz[i]==0) ++rs,dfs(i);                

   cout<<rs<<'\n'; 
    
 return 0;   
}