Pagini recente » Cod sursa (job #612822) | Cod sursa (job #1210626) | Cod sursa (job #2949022) | Cod sursa (job #3277426) | Cod sursa (job #2461288)
#include <bits/stdc++.h>
#define Nmax 100005
#define pi pair<int, int>
#define pb push_back
#define mp make_pair
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
int N, M, C, curr;
int lev[Nmax], best[Nmax]; //dfn si low
vector <int> graph[Nmax], ans[Nmax], comp;
bool vis[Nmax], done[Nmax];
void DFS(int node,int father) {
vis[node] = 1;
lev[node] = best[node] = lev[father] + 1;
comp.pb(node);
for (auto it: graph[node])
if (vis[it] == 0) {
DFS(it, node);
best[node] = min(best[node], best[it]);
if (best[it] >= lev[node]) { //componenta biconexa
++C;
while (!comp.empty() && comp.back() != node) {
ans[C].pb(comp.back());
comp.pop_back();
}
ans[C].pb(node);
}
}
else if (it != father) best[node] = min(best[node], lev[it]);
}
int main()
{
f >> N >> M;
for (int i = 1; i <= M; ++i) {
int x, y;
f >> x >> y;
graph[x].pb(y);
graph[y].pb(x);
}
DFS(1, 0);
g << C << '\n';
for (int i = 1; i <= C; ++i) {
for (auto it: ans[i])
g << it << " ";
g << "\n";
}
return 0;
}