Pagini recente » Cod sursa (job #2912529) | Cod sursa (job #2682218) | Cod sursa (job #1944971) | Cod sursa (job #787575) | Cod sursa (job #2888930)
#include <vector>
#include <string>
#include <iostream>
#include <set>
#include <fstream>
#include <iostream>
#include <queue>
#include <stack>
using std::vector;
using std::string;
using std::ifstream;
using std::ofstream;
using std::set;
using std::pair;
using std::queue;
using std::stack;
#define oo 0x3f3f3f3f
class Solve {
private:
string input_file;
string output_file;
vector<int>* graf;
vector<int> dfn, low;
stack<int> s;
vector<vector<int>> result;
int n, m;
void read() {
ifstream in(input_file);
in >> n >> m;
graf = new vector<int>[n + 1];
dfn.resize(n + 1, 0);
low.resize(n + 1, 0);
int x, y;
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 lvl) {
dfn[node] = low[node] = lvl;
s.push(node);
for (const int& vecin : graf[node]) {
if (dfn[vecin]) {
low[node] = std::min(low[node], dfn[vecin]);
}
else {
dfs(vecin, lvl + 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:
Solve(const string& input_file, const string& output_file) : input_file{ input_file }, output_file{ output_file }{};
void print() {
ofstream out(output_file);
solve();
out << result.size() << '\n';
for (const auto& componenta : result) {
for (const auto& node : componenta) {
out << node << " ";
}
out << '\n';
}
out.close();
}
~Solve() {
delete[] graf;
}
};
int main() {
Solve s = Solve("biconex.in", "biconex.out");
s.print();
return 0;
}