Pagini recente » Diferente pentru home intre reviziile 903 si 544 | Monitorul de evaluare | Diferente pentru home intre reviziile 903 si 578 | Monitorul de evaluare | Cod sursa (job #1478416)
#include <iostream>
#include <vector>
using namespace std;
void dfs(int sursa, vector<int>* vecini, bool* visited, int& nr_left) {
for (int i = 0; i < vecini[sursa].size(); i++) {
int vecin = vecini[sursa][i];
if (!visited[vecin]) {
nr_left--;
visited[vecin] = true;
dfs(vecin, vecini, visited, nr_left);
}
}
}
int main() {
freopen("dfs.in", "r", stdin);
freopen("dfs.out", "w", stdout);
int n, m;
scanf("%i%i", &n, &m);
vector<int>* vecini = new vector<int>[n];
for (int i = 0; i < m; i++) {
int x, y;
scanf("%i%i", &x, &y);
x--;
y--;
vecini[x].push_back(y);
vecini[y].push_back(x);
}
bool* visited = new bool[n];
for (int i = 0; i < n; i++) {
visited[i] = false;
}
int nr_left = n;
int nr_comp_conexe = 0;
while(nr_left != 0) {
nr_comp_conexe++;
int start = -1;
for (int i = 0; i < n; i++) {
if (!visited[i]) {
start = i;
break;
}
}
nr_left--;
visited[start] = true;
dfs(start, vecini, visited, nr_left);
}
printf("%i", nr_comp_conexe);
fclose(stdin);
fclose(stdout);
return 0;
}