Cod sursa(job #513103)
Utilizator | Liviu P. BeRReT | Data | 15 decembrie 2010 08:49:47 |
---|---|---|---|
Problema | Parcurgere DFS - componente conexe | Scor | 50 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.47 kb |
#include <iostream.h>
#include <fstream.h>
#define DIM 1002
int a[DIM][DIM], N, M, nr1, nr2, i, nc, v[DIM];
ifstream f("dfs.in");
ofstream g("dfs.out");
void df(int, int);
int main (){
f>>N>>M;
for(i=1;i<=M;i++){
f>>nr1>>nr2;
a[nr1][nr2]=a[nr2][nr1]=1;}
nc=0;
for(i=1;i<=N;i++)
if(v[i]==0){
nc++;
df(i,nc);
}
g<<nc;
f.close();
return 0;
}
void df(int i, int k){
v[i]=k;
for(int p=1;p<=N;p++)
if(a[i][p]==1 && v[p]==0)
df(p,k);
}