Pagini recente » Cod sursa (job #2672881) | Cod sursa (job #2859491) | Cod sursa (job #363770) | Cod sursa (job #451707) | Cod sursa (job #2771181)
#include <fstream>
#include <unordered_set>
#include <unordered_map>
#include <vector>
using namespace std;
int findNoSCC(unordered_map<int, unordered_set<int>> &adj) {
vector<bool> visited(adj.size(), false);
vector<bool> isOnStack(adj.size(), false);
vector<int> stack;
int noSCC = 0;
for (auto &nodeAdj : adj) {
int w = nodeAdj.first;
if (visited[w])
continue;
stack.push_back(w);
isOnStack[w] = true;
while (!stack.empty()) {
int node = stack[stack.size() - 1];
stack.pop_back();
isOnStack[node] = false;
for (const int &u : adj[node]) {
if (!visited[u] && !isOnStack[u]) {
stack.push_back(u);
isOnStack[u] = true;
}
}
visited[node] = true;
}
noSCC++;
}
return noSCC;
}
int main(void) {
const string INPUT_FILENAME = "dfs.in";
const string OUTPUT_FILENAME = "dfs.out";
ifstream in(INPUT_FILENAME);
ofstream out(OUTPUT_FILENAME);
int N, M, i;
in >> N >> M;
unordered_map<int, unordered_set<int>> adj;
adj.reserve(N);
for (int i = 0; i < N; i++)
adj[i] = {};
int x, y;
for (i = 0; i < M; i++) {
in >> x >> y;
--x;
--y;
adj[x].insert(y);
adj[y].insert(x);
}
int res = findNoSCC(adj);
out << res;
in.close();
out.close();
return 0;
}