Pagini recente » Cod sursa (job #732613) | Cod sursa (job #126942) | Cod sursa (job #1392941) | Cod sursa (job #3171898) | Cod sursa (job #2134147)
#include <iostream>
#include <vector>
#include <fstream>
#include <stack>
#define NMAX (100000 + 3)
#define MMAX (1000000 + 3)
using namespace std;
void DFS(int n, int source, vector<int> neighbors[], bool visited[]) {
stack<int> stack;
stack.push(source);
visited[source] = true;
while (!stack.empty()) {
int node = stack.top();
stack.pop();
for (auto const &ngbr : neighbors[node]) {
if (!visited[ngbr]) {
visited[ngbr] = true;
stack.push(ngbr);
}
}
}
}
int main() {
ifstream f("dfs.in");
ofstream g("dfs.out");
vector<int> neighbors[NMAX];
bool visited[NMAX];
int n, m, i, j;
f >> n >> m;
for (; m; --m) {
int x, y;
f >> x >> y;
neighbors[x].push_back(y);
neighbors[y].push_back(x);
}
int connected_comp = 0;
for (i = 1; i <= n; ++i) {
visited[i] = false;
}
for (i = 1; i <= n; ++i) {
if (!visited[i]) {
++connected_comp;
DFS(n, i, neighbors, visited);
}
}
g << connected_comp;
return 0;
}