Pagini recente » Cod sursa (job #865231) | Borderou de evaluare (job #1876838) | Cod sursa (job #1876746) | Cod sursa (job #1912450) | Cod sursa (job #1915071)
#include <iostream>
#include <cstdio>
#include <vector>
#include <stack>
#include <bitset>
using namespace std;
const int Nmax = 100005;
const int Mmax = 200005;
vector < int > G[Mmax];
stack < pair <int, int > > st;
int N,M;
int nivel[Nmax], sus[Nmax];
void Read()
{
freopen("biconex.in", "r", stdin);
freopen("biconex.out", "w", stdout);
scanf("%d%d", &N, &M);
for(int i=1; i<=M; ++i)
{
int x,y;
scanf("%d%d", &x, &y);
G[x].push_back(y);
G[y].push_back(x);
}
}
int nr=0;
bitset <Nmax> viz;
vector < int > rez[Nmax];
void Transcript(int el)
{
nr++;
while(st.top().second!=el)
{
rez[nr].push_back(st.top().second);
st.pop();
}
rez[nr].push_back(st.top().second);
rez[nr].push_back(st.top().first);
st.pop();
}
void dfs(int x, int dad)
{
viz[x]=1;
nivel[x]=nivel[dad]+1;
sus[x]=nivel[x];
vector <int>::iterator it;
for(it=G[x].begin(); it!=G[x].end(); ++it)
{
if(*it==dad)
continue;
else if(!viz[*it])
{
st.push(make_pair(x,*it));
dfs(*it,x);
sus[x]=min(sus[*it], sus[x]);
if(sus[*it]>=nivel[x])
Transcript(*it);
}
else
sus[x]=min(nivel[*it], sus[x]);
}
}
int afi[Mmax];
void Print()
{
cout<<nr<<"\n";
for(int i=1; i<=nr; ++i)
{int ind=0;
for(vector <int>::iterator it=rez[i].begin(); it!=rez[i].end(); ++it)
afi[++ind]=*it;
for(int ind1=ind; ind1>=1; ind1--)
cout<<afi[ind1]<<" ";
cout<<"\n";
}
}
int main()
{
Read();
for(int i=1; i<=N; ++i)
if(!viz[i])
dfs(i,0);
Print();
return 0;
}