Pagini recente » Cod sursa (job #1278288) | Cod sursa (job #292676) | Cod sursa (job #1750485) | Cod sursa (job #2944769) | Cod sursa (job #2888569)
#include <vector>
#include <string>
#include <fstream>
#include <stack>
#include <iostream>
using std::vector;
using std::string;
using std::stack;
using std::ifstream;
using std::ofstream;
class Biconex {
private:
string input_file;
string output_file;
stack<int> s;
vector<int> dfn, low;
vector<int>* graf;
vector<vector<int>> result;
void read() {
ifstream in(input_file);
int n, m, x, y;
in >> n >> m;
dfn.resize(n + 1, 0);
low.resize(n + 1, 0);
graf = new vector<int>[n + 1];
for(int i = 1;i <= m;++i){
in >> x >> y;
graf[x].push_back(y);
graf[y].push_back(x);
}
in.close();
}
void dfs(int node, int level) {
dfn[node] = low[node] = level;
s.push(node);
for (const auto& vecin : graf[node]) {
if (dfn[vecin]) {
low[node] = std::min(low[node], dfn[vecin]);
}
else {
dfs(vecin, level + 1);
low[node] = std::min(low[node], low[vecin]);
if (low[vecin] >= dfn[node]) {
vector<int> componenta;
componenta.push_back(node);
int x;
do {
x = s.top();
s.pop();
componenta.push_back(x);
} while (x != vecin);
result.push_back(componenta);
}
}
}
}
void solve() {
read();
dfs(1, 1);
}
public:
Biconex(const string& input_file, const string& output_file) : input_file{ input_file }, output_file{ output_file }{};
void print() {
solve();
ofstream out(output_file);
out << result.size()<<'\n';
for (const auto& componenta : result) {
for (const auto& nod : componenta) {
out << nod << " ";
}
out << '\n';
}
out.close();
}
~Biconex() {
delete[] graf;
}
};
int main() {
Biconex biconex = Biconex("biconex.in", "biconex.out");
biconex.print();
return 0;
}