Pagini recente » Cod sursa (job #2670537) | Cod sursa (job #1935768) | Cod sursa (job #1086687) | Cod sursa (job #1454489) | Cod sursa (job #2186289)
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5;
vector < int > g[MAXN + 1], stk;
vector < vector < int > > bcc;
int level[MAXN + 1], low[MAXN + 1];
inline void add_comp(int node, int son) {
vector < int > comp;
comp.push_back(node);
do {
comp.push_back(stk.back());
stk.pop_back();
} while (comp.back() != son);
bcc.push_back(comp);
}
void bicon_dfs(int node, int father) {
low[node] = level[node] = level[father] + 1;
stk.push_back(node);
for (auto it : g[node])
if (it ^ father)
if (level[it])
low[node] = min(low[node], level[it]);
else {
bicon_dfs(it, node);
low[node] = min(low[node], low[it]);
if (level[node] <= low[it])
add_comp(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();
bicon_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;
}