Pagini recente » Cod sursa (job #2079686) | Cod sursa (job #1587953) | Cod sursa (job #342414) | Cod sursa (job #3152114) | Cod sursa (job #1181034)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <stdlib.h>
using namespace std;
int main() {
ifstream in;
in.open("dfs.in");
ofstream out;
out.open("dfs.out");
int N, M, i, nod, n1, n2, vecin, contor = 0;
in >> N >> M;
vector<int> graf[N + 1];
int *visited = (int*)calloc(N + 1, sizeof(int));
vector<int>::iterator it;
stack<int> s;
for (i = 0; i < M; i++) {
in >> n1 >> n2;
if (n1 != n2) {
graf[n1].push_back(n2);
graf[n2].push_back(n1);
}
}
for (i = 1; i <= N; i++) {
if (visited[i] == 0) {
contor++;
s.push(i);
while (!s.empty()) {
nod = s.top();
vecin = -1;
for (it = graf[nod].begin(); it != graf[nod].end(); it++) {
if (visited[*it] == 0) {
vecin = *it;
break;
}
}
if (vecin != -1) { // daca exista vecin
visited[vecin] = 1;
s.push(vecin);
}
else {
visited[nod] = -1;
s.pop();
}
}
}
}
out << contor;
in.close();
out.close();
return 0;
}