Pagini recente » Cod sursa (job #1419210) | Cod sursa (job #2167672) | Cod sursa (job #210434) | Cod sursa (job #1355452) | Cod sursa (job #3283803)
#include <fstream>
#include <vector>
using namespace std;
ifstream cin("biconex.in");
ofstream cout("biconex.out");
struct Info {
int node;
int nxt;
Info() = default;
Info(int node, int nxt) : node(node), nxt(nxt) {}
};
int n, m;
vector<vector<int>> graph, biconex;
void read() {
cin >> n >> m;
graph.resize(n + 1);
for (int i = 1; i <= m; i++) {
int a, b;
cin >> a >> b;
graph[a].emplace_back(b);
graph[b].emplace_back(a);
}
}
void dfs(int node, int par, int &time, vector<int> &low, vector<int> &disc, vector<int> &curr_stk) {
disc[node] = ++ time;
low[node] = time;
curr_stk.emplace_back(node);
for (auto it : graph[node]) {
if (it == par) {
continue;
}
if (disc[it] == -1) {
dfs(it, node, time, low, disc, curr_stk);
low[node] = min(low[node], low[it]);
if (low[it] >= disc[node]) {
vector<int> temp;
while (!curr_stk.empty() && curr_stk.back() != node) {
temp.emplace_back(curr_stk.back());
curr_stk.pop_back();
}
temp.emplace_back(node);
if (temp.empty()) {
return;
}
biconex.emplace_back(temp);
}
}
else {
low[node] = min(low[node], low[it]);
}
}
}
void solve() {
vector<int> low(n + 1, -1), disc(n + 1, -1), curr_stk;
vector<bool> fr_stk(n + 1);
int time = 0;
for (int i = 1; i <= n; i++) {
if (disc[i] != -1) {
continue;
}
dfs(i, 0, time, low, disc, curr_stk);
}
cout << biconex.size() << "\n";
for (auto it1 : biconex) {
for (auto it2 : it1) {
cout << it2 << " ";
}
cout << "\n";
}
}
int main()
{
read();
solve();
return 0;
}