Cod sursa(job #669211)

Utilizator ion824Ion Ureche ion824 Data 26 ianuarie 2012 15:05:42
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.91 kb
#include<fstream>
using namespace std;
int n,m,cnt; bool viz[100005];
typedef struct nod{
        int info;
        nod *next;
        }*pNod;
pNod v[100005]; 

void add(pNod &dest,int val){
     pNod p;
     p = new nod;
     p -> info = val;
     p -> next = dest;
     dest = p;    
     }

void readdata(){
     ifstream fin("dfs.in");
     int x,y;
     fin>>n>>m; 
     for(int i=1;i<=m;++i){
            fin>>x>>y;
            add(v[x],y);
            add(v[y],x);
             }   
     fin.close();          
     }        

void DFS(int nod){
     pNod p;
     viz[nod]=1;
     for(p=v[nod]; p!=NULL; p=p->next) if(!viz[p->info])DFS(p->info);     
     }

int main(void){
    ofstream fout("dfs.out");
    readdata();
    for(int i=1;i<=n;++i)
    if(!viz[i]){ 
                 ++cnt; 
                 DFS(i); 
                 }
    fout<<cnt; fout.close();
 return 0;   
}