Pagini recente » Cod sursa (job #2772169) | Cod sursa (job #1436593) | Cod sursa (job #804187) | Cod sursa (job #2396325) | Cod sursa (job #2113047)
//componente biconexe
#include <bits/stdc++.h>
using namespace std;
int n, m, Sol;
int low[100005], lev[100005];
vector <int> v[100005];
vector <int> C[100005];
stack <pair <int, int> > st;
inline void cb(int x, int y){
int a, b;
do{
a = st.top().first;
b = st.top().second;
st.pop();
C[Sol].push_back(b);
}while(!(a == x && b == y));
C[Sol].push_back(a);
}
inline void dfs(int nod, int TT, int k){
low[nod] = lev[nod] = k;
for(auto it : v[nod]){
if(it != TT){
if(lev[it] == 0){
st.push(make_pair(nod, it));
dfs(it, nod, k + 1);
if(lev[nod] <= low[it]){
++Sol;
cb(nod, it);
}
low[nod] = min(low[nod], low[it]);
}
else low[nod] = min(low[nod], lev[it]);
}
}
}
int main()
{
freopen("biconex.in", "r", stdin);
freopen("biconex.out", "w", stdout);
scanf("%d%d", &n, &m);
int x, y;
for(int i = 1; i <= m ; ++i){
scanf("%d%d", &x, &y);
v[x].push_back(y);
v[y].push_back(x);
}
dfs(1, 0, 1);
printf("%d\n", Sol);
for(int i = 1; i <= Sol ; ++i){
sort(C[i].begin(), C[i].end());
for(auto it : C[i]) printf("%d ", it);
printf("\n");
}
return 0;
}