Pagini recente » Cod sursa (job #2847255) | Cod sursa (job #1639287) | Cod sursa (job #839244) | Cod sursa (job #222397) | Cod sursa (job #2771185)
#include <fstream>
#include <vector>
#include <list>
#include <iostream>
using namespace std;
int findNoSCC(list<int> *adj, const int N) {
vector<bool> visited(N, false);
vector<bool> isOnStack(N, false);
vector<int> stack;
int noSCC = 0;
for (int v = 0; v < N; v++) {
if (visited[v])
continue;
stack.push_back(v);
isOnStack[v] = 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;
list<int> adj[N];
int x, y;
for (i = 0; i < M; i++) {
in >> x >> y;
--x;
--y;
adj[x].push_back(y);
adj[y].push_back(x);
}
int res = findNoSCC((list<int> *) adj, N);
out << res;
in.close();
out.close();
return 0;
}