Pagini recente » Cod sursa (job #1380135) | Cod sursa (job #804372) | Cod sursa (job #1371878) | Cod sursa (job #1306021) | Cod sursa (job #2199214)
#include <bits/stdc++.h>
using namespace std;
ifstream f ("dfs.in");
ofstream g ("dfs.out");
vector <int> adiac[100005];
stack <int> coada;
int vizitati[100005];
int nNoduri, nMuchii;
int componente;
void citire();
void rezolvare(int nod) {
// cout << "apelare" << '\n';
coada.push(nod);
vizitati[nod] = 1;
while (!coada.empty()) {
nod = coada.top();
coada.pop();
vizitati[nod] = 1;
for (int i = 0; i < adiac[nod].size(); ++i) {
// cout << nodCurent << ' ' << i << '\n';
if (vizitati[adiac[nod][i]] == 0) {
coada.push(adiac[nod][i]);
vizitati[adiac[nod][i]] = 1;
}
}
}
}
int main()
{
citire();
for (int i = 1; i <= nNoduri; ++i) {
if (vizitati[i] == 0) {
++componente;
rezolvare(i);
}
}
g << componente;
return 0;
}
void citire() {
int prim, sec;
f >> nNoduri >> nMuchii;
for (int i = 1; i <= nMuchii; ++i) {
f >> prim >> sec;
adiac[prim].push_back(sec);
adiac[sec].push_back(prim);
}
}