Pagini recente » Cod sursa (job #2190714) | Cod sursa (job #1569589) | Cod sursa (job #2660168) | Cod sursa (job #1107091) | Cod sursa (job #2685575)
#include <bits/stdc++.h>
//#pragma GCC optimize ("03")
#define FastIO ios_base::sync_with_stdio(false) , cin.tie(0) , cout.tie(0)
#define FILES freopen("biconex.in" , "r" , stdin) , freopen("biconex.out" , "w" , stdout)
#define pii pair < int , int >
#define pb push_back
using namespace std;
const int N = 1e5 + 10;
int n , m , x , y;
vector < int > v[N] , compbi[N];
stack < pii > s;
int h[N] , low[N];
bool mark[N];
int cnt;
void comp(pii t)
{
++cnt;
while(s.top() != t)
{
compbi[cnt].pb(s.top().second);
s.pop();
}
compbi[cnt].pb(s.top().first);
compbi[cnt].pb(s.top().second);
s.pop();
}
void dfs(int w , int p , int height)
{
mark[w] = 1;
h[w] = height;
low[w] = height;
for(auto i : v[w])
if(!mark[i])
{
s.push({w , i});
dfs(i , w , height + 1);
low[w] = min(low[w] , low[i]);
if(p == -1 && v[w].size() > 1)
comp({w , i});
else if(low[i] >= height)
comp({w , i});
}
else if(i != p)
low[w] = min(low[w] , low[i]);
}
signed main()
{
#ifndef ONLINE_JUDGE
FastIO , FILES;
#endif
cin >> n >> m;
for(int i = 1 ; i <= m ; i++)
{
cin >> x >> y;
v[x].pb(y);
v[y].pb(x);
}
for(int i = 1 ; i <= n ; i++)
if(!mark[i])
dfs(i , -1 , 0);
cout << cnt << '\n';
for(int i = 1 ; i <= cnt ; i++ , cout << '\n')
for(auto j : compbi[i])
cout << j << ' ';
return 0;
}