Pagini recente » Cod sursa (job #2902079) | Cod sursa (job #480140) | Istoria paginii runda/simulare__1 | Cod sursa (job #133399) | Cod sursa (job #2079705)
#include <fstream>
#include <iostream>
#include <vector>
#include <deque>
using namespace std;
vector<int> L[100010]; /// 100000 e vectori (o matrice cu 100000 de linii goale)
ifstream fin ("dfs.in");
ofstream fout("dfs.out");
int n, m, x, y, sol, v[100010], i, j, nod, vecin;
deque<int> c;
int main () {
fin>>n>>m;
for (i=1;i<=m;i++) {
fin>>x>>y;
L[x].push_back(y); /// lista de vecini a lui x, adica un vector cu toti vecinii lui x,
/// memorati unul langa altul (incapand cu pozitia 0).
L[y].push_back(x);
}
for (i=1;i<=n;i++) {
if (v[i] == 0) {
sol ++;
c.push_back(i);
v[i] = 1;
while (!c.empty()) {
nod = c.front();
c.pop_front();
for (j=0;j<L[ nod ].size(); j++) {
vecin = L[nod][j];
if ( v[ vecin ] == 0 ) {
c.push_back(vecin);
v[vecin] = 1;
}
}
}
}
}
fout<<sol;
return 0;
}