Pagini recente » Cod sursa (job #3232782) | Cod sursa (job #2809473) | Cod sursa (job #1835861) | Cod sursa (job #3317169) | Cod sursa (job #3313137)
#include <fstream>
#include <vector>
#include <queue>
struct Node{
std::vector<int> edges;
int utHossz;
Node(){
utHossz = -1;
}
void addEdge(int x){
edges.push_back(x);
}
int nrEdges(){
return edges.size();
}
};
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].utHossz == -1){
std::queue<Node> varoLista;
nodes[i].utHossz = 0;
varoLista.push(nodes[i]);
while(!varoLista.empty()){
Node jelenlegi = varoLista.front();
varoLista.pop();
for(int j = 0; j < jelenlegi.nrEdges(); j++){
if(nodes[jelenlegi.edges[j]].utHossz == -1){
nodes[jelenlegi.edges[j]].utHossz = jelenlegi.utHossz + 1;
varoLista.push(nodes[jelenlegi.edges[j]]);
}
}
}
nr++;
}
}
kim << nr;
bem.close();
kim.close();
}