Pagini recente » Cod sursa (job #830286) | Cod sursa (job #1932825) | Cod sursa (job #545220) | Cod sursa (job #3166496) | Cod sursa (job #1113935)
#include<cstdio>
#include<vector>
#include<stack>
#include<algorithm>
#define N_MAX 100010
#define pb push_back
#define mp make_pair
#define INF (1<<31)-5
using namespace std;
stack < pair<int,int> > Q;
vector <int> G[N_MAX], cop;
vector < vector<int> > Sol;
int a[N_MAX],low[N_MAX],niv[N_MAX],T[N_MAX],N,NR;
bool use[N_MAX];
inline void Write_Sol()
{
vector <int> :: iterator it;
printf("%d\n",Sol.size());
for (int i=0;i<Sol.size();++i)
{
for (it=Sol[i].begin();it!=Sol[i].end();++it)
printf("%d ",*it);
printf("\n");
}
}
inline void ins(int x,int niv)
{
if (a[x]==niv) return;
cop.pb(x); a[x]=niv;
}
inline void Load_Sol(int x,int Tx,int NR)
{
int a,b;
cop.clear();
do
{
a=(Q.top()).first; b=(Q.top()).second;
Q.pop();
ins(a,NR); ins(b,NR);
}
while (a!=x && b!=Tx);
Sol.pb(cop);
}
inline void DFS(int Nod,int k)
{
niv[Nod]=k; low[Nod]=k; use[Nod]=true;
for (vector <int> :: iterator it=G[Nod].begin();it!=G[Nod].end();++it)
{
if (!use[*it])
{
use[*it]=true; T[*it]=Nod; Q.push(mp(Nod,*it));
DFS(*it,k+1);
low[Nod]=min(low[Nod],low[*it]); NR++;
if (low[*it]>=niv[Nod]) Load_Sol(Nod,T[Nod],NR);
}
else low[Nod]=min(low[Nod],niv[*it]);
}
}
inline void Load_Data(int &N)
{
int M,x,y;
scanf("%d%d",&N,&M);
for (int i=1;i<=M;++i)
{scanf("%d%d",&x,&y); G[x].pb(y); G[y].pb(x);}
for (int i=1;i<=N;++i) {T[i]=0; use[i]=false;}
}
int main()
{
freopen("biconex.in","r",stdin);
freopen("biconex.out","w",stdout);
Load_Data(N);
for (int i=1;i<=N;++i)
if (!use[i]) DFS(i,1);
Write_Sol();
fclose(stdin); fclose(stdout);
return 0;
}