Pagini recente » Cod sursa (job #161670) | Cod sursa (job #1698773) | Cod sursa (job #287881) | Cod sursa (job #880560) | Cod sursa (job #3152312)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <deque>
#include <iomanip>
#include <vector>
#pragma GCC optimize("O3")
#define fi first
#define se second
#define pb push_back
#define pf push_front
using namespace std;
ifstream fin ("biconex.in");
ofstream fout ("biconex.out");
typedef long long ll;
const ll Nmax=1e5+5, inf=1e9+5;
using pll=pair<ll, ll>;
int n, m, nrc;
vector <int> ad[Nmax];
int lvl[Nmax];
bool vis[Nmax];
stack <int> st;
vector <int> sol[Nmax];
int dfs(int nod, int p){
if (vis[nod])
return lvl[nod];
vis[nod]=1;
lvl[nod]=lvl[p]+1;
st.push(nod);
int mn=lvl[nod];
for (auto it:ad[nod]){
int crt;
if (it!=p && !vis[it]){
crt=dfs(it, nod);
mn=min(mn, crt);
if (crt>=lvl[nod]){
while (st.top()!=it){
sol[nrc].pb(st.top());
st.pop();
}
sol[nrc].pb(st.top());
sol[nrc].pb(nod);
st.pop();
nrc++;
}
}
else if (it!=p){
crt=dfs(it, nod);
mn=min(mn, crt);
}
}
return mn;
}
inline void hopcraft_tarjan(){
lvl[n]=-1;
for (int i=0; i<n; i++)
if (!vis[i])
dfs(i, n);
}
int main()
{
/*ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);*/
fin>>n>>m;
int a, b;
for (int i=0; i<m; i++){
fin>>a>>b;
a--; b--;
ad[a].pb(b);
ad[b].pb(a);
}
hopcraft_tarjan();
fout<<nrc<<'\n';
for (int i=0; i<nrc; i++){
for (auto it:sol[i])
fout<<it+1<<' ';
fout<<'\n';
}
return 0;
}