Cod sursa(job #680658)

Utilizator Stefan93Mihalache Stefan Stefan93 Data 15 februarie 2012 20:04:26
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.67 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;  
}