Pagini recente » Cod sursa (job #2759372) | Cod sursa (job #1636663) | Cod sursa (job #866376) | Cod sursa (job #2468583) | Cod sursa (job #1782741)
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100000;
vector <int> g[MAXN + 1];
vector <vector <int>> ans;
int lev[MAXN + 1], low[MAXN + 1];
struct StackNode {
int nod, son;
} x;
stack <StackNode> st;
inline int minim(int a, int b) {
if (a < b)
return a;
return b;
}
inline void add_comp(int node) {
vector <int> comp;
do {
x = st.top();
comp.push_back(x.son);
st.pop();
} while (x.nod != node);
comp.push_back(node);
ans.push_back(comp);
}
void dfs(int node, int parent) {
lev[node] = low[node] = lev[parent] + 1;
for (auto i : g[node])
if (i != parent)
if (lev[i])
low[node] = minim(low[node], lev[i]);
else {
st.push({node, i});
dfs(i, node);
low[node] = minim(low[node], low[i]);
if (low[i] >= lev[node])
add_comp(node);
}
}
int main()
{
int n, m, x, y;
ifstream fin("biconex.in");
fin >> n >> m;
for (int i = 0; i < m; ++i) {
fin >> x >> y;
g[x].push_back(y);
g[y].push_back(x);
}
fin.close();
for (int i = 1; i <= n; ++i)
if (lev[i] == 0)
dfs(i, 0);
ofstream fout("biconex.out");
fout << ans.size() << '\n';
for (auto i : ans) {
for (auto j : i)
fout << j << " ";
fout << '\n';
}
fout.close();
return 0;
}