Pagini recente » Cod sursa (job #525334) | Cod sursa (job #2942381) | Cod sursa (job #980992) | Cod sursa (job #2539522) | Cod sursa (job #2540689)
#include <bits/stdc++.h>
#define NMAX 100005
#define cin fin
#define cout fout
#define pb push_back
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
int n, m;
int sol;
vector<int> mat[NMAX];
vector<int> G[NMAX];
int used[NMAX], L[NMAX], nv[NMAX], t[NMAX];
vector< pair<int, int> > st;
void read();
void DFS(int nod);
void processing(int tata, int nod);
int main()
{
read();
for(int i=1; i<=n; ++i)
{
if(used[i]) continue;
nv[i]=1;
used[i]=1;
DFS(i);
}
cout<<sol<<'\n';
for(int i=0; i<sol; ++i)
{
for(auto it:mat[i])
cout<<it<<' ';
cout<<'\n';
}
return 0;
}
void processing(int tata, int nod)
{
set<int> s;
while(true)
{
s.insert(st.back().first);
s.insert(st.back().second);
if(st.back().first==tata && st.back().second==nod)
{
st.pop_back();
break;
}
st.pop_back();
}
for(auto it:s)
mat[sol].pb(it);
++sol;
}
void DFS(int nod)
{
L[nod]=nv[nod];
for(auto it:G[nod])
{
if(it!=t[nod] && nv[it]<nv[nod] && nv[it])
st.pb(make_pair(nod, it));
if(!used[it])
{
used[it]=1; nv[it]=nv[nod]+1; t[it]=nod;
st.pb(make_pair(nod, it));
DFS(it);
if(L[it]<L[nod])
L[nod]=L[it];
if(L[it]>=nv[nod])
processing(nod, it);
}
else if(it!=t[nod] && L[nod]>nv[it])
L[nod]=nv[it];
}
}
void read()
{
cin>>n>>m;
for(int i=1; i<=m; ++i)
{
int x, y;
cin>>x>>y;
G[x].pb(y);
G[y].pb(x);
}
}