Pagini recente » Cod sursa (job #443660) | Cod sursa (job #2769356) | Cod sursa (job #2825384) | Cod sursa (job #2446909) | Cod sursa (job #2580256)
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
using std::cout;
using std::endl;
using std::cin;
using std::vector;
using std::queue;
using std::stack;
using std::fstream;
using std::ios;
using std::sort;
fstream file1("dfs.in", ios::in);
fstream file2("dfs.out", ios::out);
int nr_noduri, nr_muchii;
vector<int> vecini[100005];
vector<bool> vizitat(100005);
int nr_comp_conex();
void form_vecini();
void dfs(int start);
int main(int argc, char** argv) {
file1 >> nr_noduri >> nr_muchii;
form_vecini();
file2 << nr_comp_conex();
file1.close();
file2.close();
return 0;
}
int nr_comp_conex() {
int count{ 0 };
for (int i{ 1 }; i <= nr_noduri; i++) {
if (!vizitat[i]) {
dfs(i);
count++;
}
}
return count;
}
void dfs(int start) {
vizitat[start] = true;
for (auto it = vecini[start].begin(); it != vecini[start].end(); it++) {
if (!vizitat[*it]) {
vizitat[*it] = true;
dfs(*it);
}
}
}
void form_vecini() {
int i, j;
while (file1 >> i >> j) {
vecini[i].push_back(j);
vecini[j].push_back(i);
}
}