Pagini recente » Cod sursa (job #1810352) | Cod sursa (job #485302) | Cod sursa (job #1218781) | Cod sursa (job #2663900) | Cod sursa (job #1992931)
#include <iostream>
#include <vector>
#include <fstream>
using namespace std;
vector<bool> vis;
vector<vector<int> > graph;
void DFS(int x) {
vis.at(x) = true;
for (int i = 0 ; i < graph.at(x).size() ; i++) {
int y = graph.at(x).at(i);
if (!vis.at(y)) {
DFS(y);
}
}
}
int main() {
ifstream in("dfs.in");
int n, m;
in >> n >> m;
graph.resize(n);
for (int i = 0 ; i < m ; i++) {
int x, y;
in >> x >> y;
x = x - 1;
y = y - 1;
graph.at(x).push_back(y);
graph.at(y).push_back(x);
}
vis.resize(n, false);
int k = 0;
for (int i = 0 ; i < vis.size() ; i++){
if (!vis.at(i)) {
DFS(i);
k++;
}
}
ofstream out("dfs.out");
out << k << "\n";
return 0;
}