Pagini recente » Cod sursa (job #1709916) | Cod sursa (job #2819984) | Cod sursa (job #2143162) | Cod sursa (job #3228845) | Cod sursa (job #2456943)
#include <fstream>
#include <vector>
#include <stack>
#define MAXN 100001
using namespace std;
ifstream f("dfs.in");
ofstream g("dfs.out");
int N, M;
vector<int> G[MAXN];
bool viz[MAXN];
void read() {
int node1, node2;
f >> N >> M;
for (int i = 1; i <= M; ++i) {
f >> node1 >> node2;
G[node1].push_back(node2);
G[node2].push_back(node1);
}
}
void dfs(int node) {
stack<int> S;
int current;
viz[node] = true;
S.push(node);
while (!S.empty()) {
current = S.top();
S.pop();
for (auto it = G[current].begin(); it != G[current].end(); ++it) {
if (viz[*it] == false) {
S.push(*it);
viz[*it] = true;
}
}
/*
In loc de iteratori:
for (int i = 0; i < G[current].size(); ++i) {
int next = G[node][i];
if (viz[next] == false) {
S.push(next);
viz[next] = true;
}
}
*/
}
}
int main()
{
int answer = 0;
read();
for (int node = 1; node <= N; ++node) {
if (viz[node] == false) {
++answer;
dfs(node);
}
}
g << answer;
return 0;
}