Cod sursa(job #598468)
| Utilizator | Data | 25 iunie 2011 21:35:01 | |
|---|---|---|---|
| Problema | Parcurgere DFS - componente conexe | Scor | 80 |
| Compilator | cpp | Status | done |
| Runda | Arhiva educationala | Marime | 0.6 kb |
#include <fstream>
using namespace std;
int n,m,x,y,i,num=0;
int a[100005][50];
bool viz[100005];
void dfs(int x)
{
int i;
viz[x]=1;
for (i=1; i<=a[x][0]; i++)
if (!viz[a[x][i]]) dfs(a[x][i]);
}
int main()
{
ifstream f("dfs.in");
ofstream g("dfs.out");
f >> n >> m;
fill_n(viz,n+1,0);
for (i=1; i<=n; i++)
a[i][0]=0;
for (i=0; i<m; i++)
{
f >> x >> y;
a[x][++a[x][0]]=y;
a[y][++a[y][0]]=x;
}
for (i=1; i<=n; i++)
if (!viz[i]) num++, dfs(i);
g << num;
return 0;
}
