Cod sursa(job #1692595)

Utilizator alex.kosnean97Cosnean Alexandru alex.kosnean97 Data 21 aprilie 2016 11:27:40
Problema Parcurgere DFS - componente conexe Scor 5
Compilator cpp Status done
Runda Arhiva educationala Marime 0.9 kb
#include <fstream>
#include <iomanip>
#include<cmath>
using namespace std;
ifstream fin("dfs.in");
ofstream fout("dfs.out");

 
int N, M, V[100005],K;
 
typedef struct celula{
    int info; 
   celula *next;
               } *arbore;
 
arbore A[100005];
 
void ADAUGA( arbore &d, int val ){
    arbore p;
    p=new celula;
    p->info=val;
    p->next=d;
    d=p;
                                }
 
void citire(){
    
    fin>>N>>M;
    int X,Y;
    int i;
    for(i=1;i<=M;++i){
        fin>>X>>Y;
        ADAUGA(A[X],Y);
        ADAUGA(A[Y],X);
                       }   
         }
 
void adincime(int h){
    arbore p=new celula;
    V[h]=1;
    for(p=A[h];p!=NULL;p=p->next) 
    if(!A[p->info]) 
    adincime(p->info);
}
 
int main()
{
    citire();
    int i;
    for(i=1; i<=N;++i) 
    if(!V[i]) 
    { K++; adincime(i); }
    
    fout<<K;
    return 0;
}