Pagini recente » Cod sursa (job #1979602) | Cod sursa (job #1409476) | Cod sursa (job #2070675) | Profil MEXANUUU | Cod sursa (job #1527401)
#include <stack>
#include <vector>
#include <fstream>
#include <iostream>
using namespace std;
bool dfs_recursive(
int n,
vector<int>& cycle,
vector<int>& seen,
vector<int>& visiting,
const vector<vector<int>>& edges)
{
visiting[n] = 1;
seen[n] = 1;
for (auto e : edges[n]) {
if (visiting[e] == 1) {
cycle.push_back(e);
return true;
}
if (!seen[e]) {
bool c = dfs_recursive(e, cycle, seen, visiting, edges);
visiting[e] = 0;
if (c) {
if (cycle[0] == e)
return false;
cycle.push_back(e);
return true;
}
}
}
return false;
}
bool dfs_iterative(
int n,
vector<int>& cycle,
vector<int>& seen,
vector<int>& visiting,
const vector<vector<int>>& edges)
{
// i is source
stack<int> fringe;
fringe.push(n);
while (!fringe.empty()) {
int next = fringe.top();
fringe.pop();
if (seen[next])
continue;
seen[next] = 1;
visiting[next] = 0;
for (auto e : edges[next]) {
if (!seen[e]) {
visiting[e] = 1;
fringe.push(e);
}
}
}
}
int main() {
ifstream f{"dfs.in"};
ofstream g{"dfs.out"};
int n, m;
f >> n >> m;
vector<vector<int>> edges(n);
for (int i = 0; i < m; i++) {
int s, d;
f >> s >> d;
s--; d--;
edges[s].push_back(d);
edges[d].push_back(s);
}
vector<int> seen(n, 0), visiting(n, 0);
int i = 0;
int comps = 0;
while (i < seen.size()) {
while (i < seen.size() && seen[i] == 1)
i++;
if (i == seen.size())
break;
// i is source
vector<int> cycle;
//dfs_iterative(i, cycle, seen, visiting, edges);
dfs_recursive(i, cycle, seen, visiting, edges);
//if (cycle.size() > 0) {
//std::cout << "Found cycle = ";
//for (auto nn : cycle) {
//std::cout << nn << " ";
//}
//std::cout << std::endl;
//}
comps++;
}
g << comps << endl;
}