Pagini recente » Cod sursa (job #929575) | Cod sursa (job #13521) | Cod sursa (job #617713) | Cod sursa (job #708258) | Cod sursa (job #1359805)
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
int N, M, ans = -1;
vector <vector <int> > components, graph;
vector <int> height, down;
stack <pair <int, int> > edges;
void DFS(int iam, int from);
int main() {
#ifdef INFOARENA
freopen("biconex.in", "r", stdin);
freopen("biconex.out", "w", stdout);
#else
#endif
int x, y, i;
scanf("%d %d", &N, &M);
graph.resize(N + 1);
height.resize(N + 1, -1);
down.resize(N + 1);
for (i = 1; i <= M; ++i) {
scanf("%d %d", &x, &y);
graph[x].push_back(y);
graph[y].push_back(x);
}
for (i = 1; i <= N; ++i) {
if (height[i] == -1) {
DFS(i, 1);
}
}
printf("%d\n", ans + 1);
for (auto cmp: components) {
for (auto x: cmp) {
printf("%d ", x);
}
printf("\n");
}
return 0;
}
void DFS(int iam, int from) {
height[iam] = height[from] + 1;
down[iam] = height[iam];
for (auto to: graph[iam]) {
if (height[to] == -1) {
edges.push({iam, to});
DFS(to, iam);
down[iam] = min(down[iam], down[to]);
if (down[to] >= height[iam]) {
components.push_back(vector <int> ());
++ans;
while (!(edges.top().first == iam && edges.top().second == to)) {
components[ans].push_back(edges.top().second);
edges.pop();
}
edges.pop();
components[ans].push_back(to);
components[ans].push_back(iam);
}
}
else if (to != from) {
down[iam] = min(down[iam], height[to]);
}
}
}