Pagini recente » Cod sursa (job #2794406) | Monitorul de evaluare | Cod sursa (job #2842731) | Cod sursa (job #389125) | Cod sursa (job #3313321)
#include <fstream>
#include <vector>
#include <queue>
struct Node{
std::vector<int> edges;
int nrEdges;
bool bejart;
Node(){
bejart = false;
nrEdges = 0;
}
void addEdge(int x){
edges.push_back(x);
nrEdges++;
}
};
void dfs(std::vector<Node> & nodes, int x){
nodes[x].bejart = true;
for(int i = 0; i < nodes[x].nrEdges; i++)
if(!nodes[nodes[x].edges[i]].bejart)
dfs(nodes, nodes[x].edges[i]);
}
int main() {
std::ifstream bem("dfs.in");
std::ofstream kim("dfs.out");
int n, m;
bem >> n >> m;
std::vector<Node> nodes(n);
for(int i = 0; i < m; i++){
int x, y;
bem >> x >> y;
x--;
y--;
nodes[x].addEdge(y);
nodes[y].addEdge(x);
}
int nr = 0;
for(int i = 0; i < n; i++){
if(!nodes[i].bejart){
dfs(nodes, i);
nr++;
}
}
kim << nr;
bem.close();
kim.close();
}