Pagini recente » Cod sursa (job #2452637) | Cod sursa (job #2819035) | Cod sursa (job #2911122) | Cod sursa (job #2911130) | Cod sursa (job #2218281)
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5;
vector < int > g[MAXN + 1], stk;
vector < vector < int > > bcc;
int lev[MAXN + 1], low[MAXN + 1];
inline void add_bcc(int node, int son) {
vector < int > comp;
do {
comp.push_back(stk.back());
stk.pop_back();
} while (comp.back() ^ son);
comp.push_back(node);
bcc.push_back(comp);
}
void dfs(int node, int father) {
low[node] = lev[node] = lev[father] + 1;
stk.push_back(node);
for (auto it : g[node])
if (it ^ father) {
if (lev[it]) {
low[node] = min(lev[it], low[node]);
} else {
dfs(it, node);
low[node] = min(low[node], low[it]);
if (low[it] >= lev[node])
add_bcc(node, it);
}
}
}
int main()
{
int n, m;
ifstream fin("biconex.in");
fin >> n >> m;
for (int i = 0; i < m; ++i) {
int x, y;
fin >> x >> y;
g[x].push_back(y);
g[y].push_back(x);
}
fin.close();
dfs(1, 0);
ofstream fout("biconex.out");
fout << bcc.size() << '\n';
for (auto comp : bcc) {
for (auto it : comp)
fout << it << " ";
fout << '\n';
}
fout.close();
return 0;
}