Cod sursa(job #627457)

Utilizator Mirc100Mircea Octavian Mirc100 Data 29 octombrie 2011 23:56:22
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.77 kb
#include <queue>
#include<stdio.h>
using namespace std;

int n,m,viz[100000];
vector<int> l[100000]; 
void dfs(int x){
     viz[x]=1;
     for(int i=0;i<l[x].size();i++)
         if (viz[l[x][i]]==0)
             dfs(l[x][i]);
     }

int main(){
   
     FILE *f;
     int i,x,y,nrc=0;
       
     f=fopen("dfs.in","r");
     fscanf(f,"%d %d",&n,&m);
     for(i=0;i<m;i++){
         fscanf(f,"%d %d",&x,&y);
         l[x-1].push_back(y-1);
         l[y-1].push_back(x-1);
     }
     fclose(f);
     
     for(i=0;i<n;i++)
         if(viz[i]==0){
              dfs(i);
              nrc++;
              }               
                 
     f=fopen("dfs.out","w");
     fprintf(f,"%d\n",nrc);
     
     fclose(f); 
     
     return 0;   
}