Pagini recente » Cod sursa (job #1129661) | Cod sursa (job #708674) | Cod sursa (job #324494) | Cod sursa (job #2431459) | Cod sursa (job #3292312)
#include <fstream>
#include <vector>
using namespace std;
int current_component = 0;
vector<int> comps;
vector<vector<int>> arcs;
void bfs(int node) {
comps[node] = current_component;
for(unsigned int i=0; i<arcs[node].size(); ++i) {
int next_node = arcs[node][i];
if (comps[next_node] == 0) {
bfs(next_node);
}
}
}
int main() {
int n, m;
fstream infile;
infile.open("dfs.in", fstream::in);
fstream outfile;
outfile.open("dfs.out", fstream::out);
infile>>n>>m;
comps.resize(n+1);
arcs.resize(n+1);
for(int i=0; i<=m; ++i) {
int s, d;
infile>>s>>d;
arcs[s].push_back(d);
arcs[d].push_back(s);
}
for(int i=1; i<=n; ++i) {
if (comps[i] == 0) {
++current_component;
bfs(i);
}
}
outfile<<current_component<<"\n";
return 0;
}