Pagini recente » Cod sursa (job #2655780) | Cod sursa (job #917124) | Cod sursa (job #272138) | Cod sursa (job #2890712) | Cod sursa (job #2986550)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#define NMAX 100000
using namespace std;
ifstream F("dfs.in");
ofstream G("dfs.out");
vector<vector<int>> g;
int usedNode[NMAX + 2];
int N, M, components = 0;
void initializeDS() {
g.resize(N + 1);
}
void Read() {
int x, y;
F >> N >> M;
initializeDS();
while (M--) {
F >> x >> y;
g[x].push_back(y);
g[y].push_back(x);
}
F.close();
}
void DFS(int sourceNode) {
int currentPivotNode, currentNode;
stack<int> st;
st.push(sourceNode);
usedNode[sourceNode] = 1;
while (!st.empty()) {
currentPivotNode = st.top();
st.pop();
if (!usedNode[currentPivotNode]) {
usedNode[currentPivotNode] = 1;
}
for (int currentNode : g[currentPivotNode]) {
if (!usedNode[currentNode]) {
st.push(currentNode);
}
}
}
}
void Solve() {
int i = 1;
while (i <= N) {
DFS(i);
components++;
do {
i++;
} while (usedNode[i] == 1);
}
}
void Print() {
G << components;
G.close();
}
int main()
{
Read();
Solve();
Print();
return 0;
}