Pagini recente » Cod sursa (job #910296) | Cod sursa (job #2519335) | Cod sursa (job #788810) | Cod sursa (job #1543518) | Cod sursa (job #3220334)
#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
#define fi first
#define sc second
using namespace std;
typedef pair<int, int> pii;
const int N = 2e5 + 5;
int n, m, dpt[N], mindpt[N];
bool vzt[N];
vector<int> g[N];
stack<pii> stk;
vector<vector<int>> bcc;
void add(int a, int b) {
bcc.push_back({});
while(!stk.empty()) {
int x = stk.top().fi, y = stk.top().sc;
stk.pop();
bcc.back().push_back(x);
bcc.back().push_back(y);
if((a == x && b == y) || (a == y && b == x))
break;
}
sort(bcc.back().begin(), bcc.back().end());
bcc.back().erase(unique(bcc.back().begin(), bcc.back().end()), bcc.back().end());
}
void dfs(int nod, int p) {
dpt[nod] = dpt[p] + 1;
mindpt[nod] = dpt[nod];
vzt[nod] = 1;
for(auto nxt : g[nod]) {
if(nxt == p)
continue;
if(!vzt[nxt]) {
stk.push({nod, nxt});
dfs(nxt, nod);
mindpt[nod] = min(mindpt[nod], mindpt[nxt]);
if(mindpt[nxt] >= dpt[nod])
add(nod, nxt);
}
else mindpt[nod] = min(mindpt[nod], dpt[nxt]);
}
}
int main()
{
freopen("biconex.in", "r", stdin);
freopen("biconex.out", "w", stdout);
cin.tie(nullptr)->sync_with_stdio(0);
cin >> n >> m;
for(int i=1; i<=m; i++) {
int a, b;
cin >> a >> b;
g[a].push_back(b);
g[b].push_back(a);
}
dfs(1, 0);
cout << bcc.size() << '\n';
for(auto comp : bcc) {
for(auto nod : comp)
cout << nod << ' ';
cout << '\n';
}
return 0;
}