Pagini recente » Cod sursa (job #380785) | Cod sursa (job #559687) | Cod sursa (job #1014901) | Cod sursa (job #701109) | Cod sursa (job #3226696)
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
const int INF = 1e9 + 69;
const int MOD = 666013;
const int MAX = 1e5 + 2;
vector<int> comp[MAX];
vector<int> adj[MAX];
int level[MAX];
bool viz[MAX];
int low[MAX];
int noComp;
int n, m;
stack<int> S;
void dfs(int nod = 1, int dad = 0) {
level[nod] = level[dad] + 1;
low[nod] = level[dad] + 1;
viz[nod] = true;
S.push(nod);
for(const int &nxt : adj[nod])
if(nxt != dad)
if(viz[nxt])
low[nod] = min(low[nod], level[nxt]);
else {
dfs(nxt, nod);
low[nod] = min(low[nod], low[nxt]);
if(low[nxt] >= level[nod]) {
++noComp;
while(S.top() != nxt) {
comp[noComp].emplace_back(S.top());
S.pop();
}
comp[noComp].emplace_back(nxt);
comp[noComp].emplace_back(nod);
S.pop();
}
}
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
freopen("biconex.in", "r", stdin);
freopen("biconex.out", "w", stdout);
cin >> n >> m;
int x, y;
for(int i = 0; i < m; i++) {
cin >> x >> y;
adj[x].emplace_back(y);
adj[y].emplace_back(x);
}
dfs();
cout << noComp << '\n';
for(int i = 1; i <= noComp; i++) {
for(const int &x : comp[i])
cout << x << ' ';
cout << '\n';
}
return 0;
}