Pagini recente » Cod sursa (job #1586144) | Cod sursa (job #1750187) | Cod sursa (job #2168352) | Cod sursa (job #3219748) | Cod sursa (job #1195168)
#include <iostream>
#include <cstdio>
#include <vector>
#include <stack>
using namespace std;
int n, m;
vector<vector<int>> adjl;
vector<int> level, low;
stack<int> t;
vector<vector<int>> bicons;
void dfs(int u, int p)
{
if (p == -1) {
level[u] = 0;
}
else {
level[u] = level[p]+1;
}
low[u] = level[u];
t.push(u);
for (auto v: adjl[u]) {
if (level[v] != -1) {
low[u] = min(low[u], level[v]);
}
else {
dfs(v, u);
low[u] = min(low[u], low[v]);
}
}
if (p != -1 && low[u] >= level[p]) {
vector<int> bicon;
while(t.top() != p) {
bicon.push_back(t.top());
t.pop();
}
bicon.push_back(p);
bicons.push_back(bicon);
}
}
int main()
{
freopen("biconex.in", "r", stdin);
freopen("biconex.out", "w", stdout);
cin >> n >> m;
adjl.resize(n);
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
u--, v--;
adjl[u].push_back(v);
adjl[v].push_back(u);
}
level.assign(n, -1);
low.resize(n);
for (int i = 0; i < n; i++) {
if (level[i] == -1) {
dfs(i, -1);
}
}
printf("%d\n", bicons.size());
for (auto bicon: bicons) {
for (auto u: bicon) {
printf("%d ", u+1);
}
printf("\n");
}
return 0;
}