Pagini recente » Cod sursa (job #1347248) | Cod sursa (job #2544234) | Cod sursa (job #180206) | Cod sursa (job #870629) | Cod sursa (job #2960553)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
const int MAX_SIZE = 100001;
vector<int> neighbors[MAX_SIZE];
int n, m, visited[MAX_SIZE], cnt;
void graph_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 curr_neighbors_num = neighbors[node].size();
for (int i = 0; i < curr_neighbors_num; ++i) {
if (!visited[neighbors[node][i]]) {
//cout << "Ne deplasam la nodul \"" << neighbors[node][i] << "\"\n\n";
graph_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]) {
graph_traversal(i);
++cnt;
//cout << "Nodul " << i << " este nodul sursa al componentei conexe cu numarul " << cnt << '\n';
}
}
fout << cnt;
return 0;
}