Pagini recente » Cod sursa (job #2886688) | Cod sursa (job #1234135) | Cod sursa (job #2590863) | Cod sursa (job #2619419) | Cod sursa (job #3183186)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
const int NMAX = 100005;
vector<int> g[NMAX];
int n, m, tin[NMAX], low[NMAX], timer;
bool vis[NMAX];
int nr_comp;
vector<int> comp[NMAX];
stack<int> st;
void dfs(int curr, int prv = -1) {
vis[curr] = true;
tin[curr] = low[curr] = ++timer;
st.push(curr);
for (auto nxt : g[curr]) {
if (nxt == prv)
continue;
if (vis[nxt]) { // back edge
low[curr] = min(low[curr], tin[nxt]);
} else {
dfs(nxt, curr);
low[curr] = min(low[curr], low[nxt]);
if (low[nxt] >= tin[curr]) { // bridge
nr_comp++;
while (!st.empty() && st.top() != nxt) {
comp[nr_comp].push_back(st.top());
st.pop();
}
if (!st.empty()) {
comp[nr_comp].push_back(st.top());
st.pop();
}
comp[nr_comp].push_back(curr);
}
}
}
}
int main() {
fin >> n >> m;
for (int i = 1; i <= m; i++) {
int x, y;
fin >> x >> y;
g[x].push_back(y);
g[y].push_back(x);
}
dfs(1);
fout << nr_comp << '\n';
for (int i = 1; i <= nr_comp; i++) {
for (auto x : comp[i]) {
fout << x << ' ';
}
fout << '\n';
}
return 0;
}