Pagini recente » Cod sursa (job #2498366) | Cod sursa (job #1210617) | Cod sursa (job #1992578) | Cod sursa (job #1577093) | Cod sursa (job #1705396)
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <utility>
#include <fstream>
#include <vector>
#include <list>
#include <stack>
void dfs(int N, int init_node, bool *visited, std::vector<std::list<int> > &adj) {
std::stack<int> s;
int curr_node;
// Adaug nodul initial
s.push(init_node);
visited[init_node] = true;
while (!s.empty()) {
curr_node = s.top();
unsigned int count = 0;
for (std::list<int>::iterator neigh = adj[curr_node].begin(); neigh != adj[curr_node].end(); neigh++) {
count++;
if (!visited[*neigh]) {
s.push(*neigh);
visited[*neigh] = true;
break;
}
if (count == adj[curr_node].size()) s.pop();
}
}
}
int main(int argc, char **argv) {
std::ifstream input("dfs.in");
if (!input.is_open()) {
std::cerr << "Cannot open input file!" << std::endl;
std::exit(-1);
}
std::ofstream output("dfs.out");
if (!output.is_open()) {
std::cerr << "Cannot open output file!" << std::endl;
input.close();
std::exit(-2);
}
// Citire Graph
int N, M, u, v;
input >> N >> M;
std::vector<std::list<int> > adj(N + 1, std::list<int>());
// DFS
int init_node = 1;
bool visited[N + 1];
std::memset(visited, true, N+1);
while(input >> u >> v) {
adj[u].push_back(v);
adj[v].push_back(u);
visited[u] = false, visited[v] = false;
}
int scc = 0;
for (int i = 0; i <= N; i++)
if (!visited[i]) {
dfs(N, init_node, visited, adj);
scc++;
}
std::cout << scc << std::endl;
input.close();
output.close();
return 0;
}