Pagini recente » Cod sursa (job #3167252) | Cod sursa (job #2192767) | Cod sursa (job #137366) | Cod sursa (job #2163656) | Cod sursa (job #2961498)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
const int MAX_SIZE = 100000;
vector<int> neighbors[MAX_SIZE + 1];
int n, m, visited[MAX_SIZE + 1], cnt;
void conex_component_traversal(int node) {
visited[node] = 1;
/*
cout << "Nodul curent este nodul \"" << node << "\"\n";
cout << "Nodurile marcate sunt: ";
for (int i = 1; i <= n; ++i) {
cout << '[' << i << "] " << visited[i] << ' ';
}
cout << '\n';
*/
int node_neighbors = neighbors[node].size();
for (int i = 0; i < node_neighbors; ++i) {
if (!visited[neighbors[node][i]]) {
//cout << "Ne deplasam la nodul \"" << neighbors[node][i] << "\"\n\n";
conex_component_traversal(neighbors[node][i]);
}
}
}
int main() {
ifstream fin("dfs.in");
ofstream fout("dfs.out");
fin >> n >> m;
for (int i = 0; i < m; ++i) {
int x, y;
fin >> x >> y;
neighbors[x].push_back(y);
neighbors[y].push_back(x);
}
/*
for (int i = 1; i <= n; ++i) {
cout << "Vecinii nodului " << i << " sunt: ";
for (int j = 0; j < neighbors[i].size(); ++j) {
cout << neighbors[i][j] << ' ';
}
cout << '\n';
}
*/
for (int i = 1; i <= n; ++i) {
if (!visited[i]) {
conex_component_traversal(i);
++cnt;
//cout << "Nodul " << i << " este nodul sursa al componentei conexe cu numarul " << cnt << '\n';
}
}
fout << cnt;
return 0;
}