Mai intai trebuie sa te autentifici.
Cod sursa(job #1710952)
Utilizator | Data | 30 mai 2016 08:16:11 | |
---|---|---|---|
Problema | Parcurgere DFS - componente conexe | Scor | 50 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.71 kb |
#include <iostream>
#include <fstream>
using namespace std;
int n,m,x,y,contor;
int matrice[1000][1000];
int vizitat[1000];
void dfs(int g){
int i;
vizitat[g] = 1;
for (i=1;i<=n;i++){
if ((vizitat[i] == 0)&&((matrice[g][i]==1) || (matrice[i][g]==1)))
dfs(i);
}
}
int main()
{
ofstream out;
out.open("dfs.out");
ifstream in;
in.open("dfs.in");
in >> n;
in >> m;
for (int i = 0; i < m; i++){
in >> x;
in >> y;
matrice[x][y] = matrice[y][x] = 1;
}
for (int i=1;i<=n;i++){
if (vizitat[i]==0){
contor++;
dfs(i);
}
}
out<<contor;
return 0;
}