Pagini recente » Cod sursa (job #1394831) | Cod sursa (job #1824799) | Cod sursa (job #615372) | Cod sursa (job #924070) | Cod sursa (job #2771180)
#include <fstream>
#include <stack>
#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);
stack<int> nodes;
int noSCC = 0;
for (auto &nodeAdj : adj) {
int w = nodeAdj.first;
if (visited[w])
continue;
nodes.push(w);
isOnStack[w] = true;
while (!nodes.empty()) {
int node = nodes.top();
nodes.pop();
isOnStack[node] = false;
for (const int &u : adj[node]) {
if (!visited[u] && !isOnStack[u]) {
nodes.push(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;
}