Pagini recente » Cod sursa (job #2456018) | Cod sursa (job #1374013) | Cod sursa (job #1084491) | Cod sursa (job #1401047) | Cod sursa (job #944384)
Cod sursa(job #944384)
#include <fstream>
#include <vector>
using namespace std;
#define DIM 100010
vector<int> L[DIM];
vector<int>::iterator it;
int c[DIM];
int v[DIM];
int n, m, k, i, j, s, p, u, prim, nc;
void coada(int s) {
c[1] = s;
v[s] = 1;
p = 1;
u = 1;
while (p<=u) {
// analizez vecinii nevizitati ai lui c[p]
prim = c[p];
for (it = L[prim].begin(); it!= L[prim].end(); it++) {
if (v[ *it ] == 0) {
u++;
c[u] = *it;
v[*it] = v[prim] + 1;
}
}
p++;
}
}
int main() {
ifstream fin("dfs.in");
ofstream fout("dfs.out");
fin >> n>>m;
for (k=1;k<=m;k++) {
fin>>i>>j;
// adaugam elementul j in lista lui i
L[i].push_back(j);
L[j].push_back(i);
// a[i][j] = 1;
}
for (i=1;i<=n;i++)
if (v[i] == 0) {
coada(i);
nc++;
}
fout<<nc<<"\n";
return 0;
}