Pagini recente » Cod sursa (job #668503) | Cod sursa (job #1713604) | Cod sursa (job #2793547) | Cod sursa (job #1386319) | Cod sursa (job #2171326)
#include <bits/stdc++.h>
using namespace std;
ifstream f ("dfs.in");
ofstream g ("dfs.out");
vector <int> listeAdiac[100005];
queue <int> nodCoada;
int n, m;
int vizitati[100005];
void citire();
//
//void dfs(int nodInitial) {
// int nodCurent;
// /// Pun nodul initial in coada si il marchez
// nodCoada.push(nodInitial);
// vizitati[nodInitial] = 1;
//
//
// /// Cat timp coada nu e goala
// while (!nodCoada.empty()) {
// /// Scot nodurile din coada
// nodCurent = nodCoada.front();
// nodCoada.pop();
//
// /// Procesez nodul ... daca are vecini, ii pun si pe ei in coada.
// for (int i = 1; i <= n; ++i) {
// if (matAdiac[nodCurent][i] == 1 && vizitati[i] == 0) {
// nodCoada.push(i);
// vizitati[i] = 1;
// }
// }
// }
//}
void dfs2(int initial) {
int nodCurent;
nodCoada.push(initial);
vizitati[initial] = 1;
while(!nodCoada.empty()) {
nodCurent = nodCoada.front();
nodCoada.pop();
for (int i = 0; i < listeAdiac[nodCurent].size(); ++i) {
if (vizitati[listeAdiac[nodCurent][i]] == 0) {
/// Pune in coada nodul care exista ca vecin
nodCoada.push(listeAdiac[nodCurent][i]);
vizitati[listeAdiac[nodCurent][i]] = 1;
}
}
}
}
void citireLista();
int main()
{
citireLista();
int contor = 0;
for(int i = 1; i <= n; ++i) {
if (vizitati[i] == 0) {
dfs2(i);
contor++;
// cout << i << ' ' << contor << '\n';
}
}
g << contor;
return 0;
}
void citireLista() {
int prim;
int secund;
f >> n >> m;
for (int i = 1; i <= m; ++i) {
f >> prim >> secund;
listeAdiac[prim].push_back(secund);
}
}
//
//void citire() {
// int prim;
// int secund;
//
// f >> n >> m;
// for (int i = 1; i <= m; ++i) {
// f >> prim >> secund;
// matAdiac[prim][secund] = 1;
// }
//}