Cod sursa(job #1357315)
| Utilizator | Data | 23 februarie 2015 21:17:47 | |
|---|---|---|---|
| Problema | Parcurgere DFS - componente conexe | Scor | 10 |
| Compilator | cpp | Status | done |
| Runda | Arhiva educationala | Marime | 0.57 kb |
#include<fstream>
#include<iostream>
using namespace std;
int a[100][100],n,m,x[100],p[100],cnt=0;
ifstream f("dfs.in");
ofstream g("dfs.out");
void citire()
{ int i,l,c;
f>>n>>m;
for(i=1;i<=m;i++)
{ f>>l>>c;
a[l][c]=1;
a[c][l]=1;
}
}
void bf(int k)
{ int i,s,d;
x[1]=k;
p[k]=1;
s=d=1;
while(s<=d)
{ for(i=1;i<=n;i++)
if(a[x[s]][i]==1 && !p[i])
{ d++;
x[d]=i;
p[i]=1;
}
s++;
}
cnt++;
}
int main()
{ citire();
int i;
for(i=1;i<=n;i++)
if(!p[i]) bf(i);
g<<cnt;
return 0;
}
