Pagini recente » Cod sursa (job #1775710) | Cod sursa (job #2468132) | Cod sursa (job #2067149) | Cod sursa (job #3250016) | Cod sursa (job #895851)
Cod sursa(job #895851)
#include <cstdio>
#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
using namespace std;
const int N = 100001;
stack<pair<int,int> > S;
vector<vector<int> > V;
vector<int> G[N];
int n,m,lvl[N],low[N];
void READ ()
{
ifstream in ("biconex.in");
in>>n>>m;
for( int x,y ; m ; --m )
{
in>>x>>y;
G[x].push_back(y);
G[y].push_back(x);
}
}
void BUILD (int x,int y)
{
vector<int> C;
pair<int,int> A;
do{
A=S.top();
S.pop();
C.push_back(A.first);
C.push_back(A.second);
}while( A.first != x || A.second != y );
sort(C.begin(),C.end());
V.push_back(C);
}
void DFS (int nod,int T,int L)
{
low[nod]=L;
lvl[nod]=L;
for( vector<int>::iterator it=G[nod].begin() ; it < G[nod].end() ; ++it )
{
if( *it == T )
continue;
if( lvl[*it] != -1 )
{
low[nod]=min(low[nod],lvl[*it]);
continue;
}
S.push(make_pair(nod,*it));
DFS ( *it , nod , L+1 );
low[nod]=min(low[nod],low[*it]);
if( lvl[nod] <= low[*it] )
BUILD ( nod , *it );
}
}
void SOLVE ()
{
for( int i=1 ; i <= n ; ++i )
lvl[i]=-1;
DFS ( 1 , 0 , 0 );
}
void OUT ()
{
freopen ("biconex.out","w",stdout);
printf("%d",V.size());
for( size_t i=0 ; i < V.size() ; ++i )
{
printf("\n%d ",V[i][0]);
for( vector<int>::iterator it=V[i].begin()+1 ; it < V[i].end() ; ++it )
if( *it != *(it-1) )
printf("%d ",*it);
}
}
int main ()
{
READ ();
SOLVE ();
OUT ();
return 0;
}