Pagini recente » Cod sursa (job #1765344) | Cod sursa (job #2984281) | Cod sursa (job #1909986) | Cod sursa (job #1495950) | Cod sursa (job #2923895)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
vector<int> neighbors_list[100000];
int n, m, x, y, list_size[100000], visited_node[100000], cc_counter;
void DFS(int node) {
if (visited_node[node]) {
return;
}
visited_node[node] = 1;
/*
cout << "Nodul curent este nodul \"" << node + 1 << "\"\n";
cout << "Nodurile marcate sunt: ";
for (int i = 0; i < n; ++i) {
cout << '[' << i + 1 << "] " << visited_node[i] << ' ';
}
cout << '\n';
*/
for (int i = 0; i < list_size[node]; ++i) {
//cout << "Ne deplasam la nodul \"" << neighbors_list[node][i] << "\"\n\n";
DFS(neighbors_list[node][i] - 1);
}
}
int main() {
ifstream fin("dfs.in");
ofstream fout("dfs.out");
fin >> n >> m;
for (int i = 0; i < m; ++i) {
fin >> x >> y;
neighbors_list[x - 1].push_back(y);
neighbors_list[y - 1].push_back(x);
++list_size[x - 1];
++list_size[y - 1];
}
/*
for (int i = 0; i < n; ++i) {
cout << "Vecinii nodului " << i + 1 << " sunt: ";
for (int j = 0; j < list_size[i]; ++j) {
cout << neighbors_list[i][j] << ' ';
}
cout << "\n\n";
}
*/
for (int i = 0; i < n; ++i) {
if (!visited_node[i]) {
//cout << "Pentru nodul " << i + 1 << ": ";
DFS(i);
++cc_counter;
/*
for (int j = 0; j < n; ++j) {
cout << '[' << j + 1 << "] " << visited_node[j] << ' ';
}
cout << "\n\n";
*/
}
}
fout << cc_counter;
return 0;
}