Cod sursa(job #1048534)

Utilizator buzu.tudor67Tudor Buzu buzu.tudor67 Data 5 decembrie 2013 23:55:35
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.93 kb
#include<fstream>
#define maxn 100001
using namespace std;
ifstream fi("dfs.in");
ofstream fo("dfs.out");

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

nod *a[maxn],*q;
bool b[maxn];
int i,n,m,nr=0;
int x,y;

void dfs(int k){
     nod *q=a[k];
     b[k]=1;
     
     while(q!=NULL){
                    if(b[q->info]==0) dfs(q->info);
                    q=q->next;
                   }
}

int main(){
    fi>>n>>m;
    
    for(i=1;i<=n;i++) { a[i]=NULL; b[i]=0; }
    
    for(i=1;i<=m;i++){
                      fi>>x>>y;
                      q=new nod; q->info=x; q->next=a[y]; a[y]=q;
                      q=new nod; q->info=y; q->next=a[x]; a[x]=q;
                     }
    
    for(i=1;i<=n;i++)
       if(b[i]==0) {
                    dfs(i);
                    nr++; 
                   }
                   
    fo<<nr;
    
    fi.close();
    fo.close();
    return 0;
}