Pagini recente » Istoria paginii runda/dau_cu_sabia/clasament | Cod sursa (job #453355) | Cod sursa (job #2212536) | Cod sursa (job #3188951) | Cod sursa (job #2190034)
#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#include <stdio.h>
#define INF 0x7fffffff
#define NMAX 100002
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
struct Nod {
int nod;
int distanta;
bool operator<(const Nod &o) const
{
return distanta > o.distanta;
}
};
vector < vector < int > > G(NMAX);
vector < int > dist(NMAX, 0);
vector < bool > vizitat(NMAX);
vector < int > cnt_nod_inQ(NMAX, 0);
int n, m, s;
bool compare (const Nod& a, const Nod& b) {
return a.distanta < b.distanta;
}
void read() {
FILE * pFile;
pFile = fopen("dfs.in", "r");
//f >> n >> m;
fscanf(pFile, "%d %d", &n, &m);
int x = 0, y = 0, dist = 0;
Nod nod_pereche;
while (m--) {
fscanf(pFile, "%d %d", &x, &y);
G[x].push_back(y);
G[y].push_back(x);
}
}
Nod constructNode(int nod, int distanta) {
Nod new_node;
new_node.nod = nod;
new_node.distanta = distanta;
return new_node;
}
void bfs(int nodSursa) {
queue<int> qNode;
qNode.push(nodSursa);
vizitat[nodSursa] = true;
while (!qNode.empty()) {
int nod = qNode.front();
qNode.pop();
for (int i = 0; i < G[nod].size(); i++) {
int nodVecin = G[nod][i];
if (!vizitat[nodVecin]) {
vizitat[nodVecin] = true;
dist[nodVecin] = dist[nod] + 1;
qNode.push(nodVecin);
}
}
}
}
int main()
{
read();
int counter = 0;
for (int i = 1; i <= n; i++) {
if (!vizitat[i]) {
counter++;
bfs(i);
}
}
FILE * pFile;
pFile = fopen("dfs.out", "w");
fprintf(pFile, "%d", counter);
return 0;
}