Pagini recente » Cod sursa (job #931322) | Cod sursa (job #568809) | Cod sursa (job #1798297) | Cod sursa (job #1975156) | Cod sursa (job #916443)
Cod sursa(job #916443)
#include<cstdio>
#include<vector>
#include<stack>
#include<algorithm>
using namespace std;
#define MAX 100001
#define pb push_back
#define mp make_pair
int N , M , low[MAX] , u[MAX] , niv[MAX] ,t[MAX], l[MAX] , k , nr , start ;
vector<int> G[MAX] ;
vector<int> Comp[MAX];
stack< pair<int,int> > ST;
void citire();
void solve();
void DF(int nod);
void Make_Comp(int nr,int x , int y);
void tipar();
int main()
{
citire();
solve();
tipar();
return 0;
}
void citire()
{
int x, y;
freopen("biconex.in" , "r" , stdin );
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);
}
}
void solve()
{
for( int i = 1 ; i <= N ; ++i )
if(!u[i])
{
u[i] = 1;
niv[i] = 1;
DF(i);
}
}
void DF(int nod)
{
u[nod] = 1;
low[nod] = niv[nod];
vector<int>::iterator it;
for( it = G[nod].begin() ; it < G[nod].end() ; ++it)
{
if(*it != t[nod] && niv[nod] > niv[*it])
ST.push(mp(nod,*it));
if(!u[*it])
{
niv[*it] = niv[nod]+1;
t[*it] = nod;
DF(*it);
if(low[*it] >= niv[nod] && ST.size())
Make_Comp(++nr,nod,*it);
if(low[*it] < low[nod])
low[nod] = low[*it];
}
else
if(low[nod] > niv[*it] && t[nod] != *it)
low[nod] = niv[*it];
}
}
void Make_Comp(int nr,int x , int y)
{
pair<int,int> M1 = mp(x,y) , M2 = mp(y,x) , M = ST.top();
while(M != M1 && M!=M2)
{
Comp[nr].pb(ST.top().second);Comp[nr].pb(ST.top().first);
ST.pop();
M = ST.top();
}
Comp[nr].pb(ST.top().second);Comp[nr].pb(ST.top().first);
ST.pop();
}
void tipar()
{
freopen("biconex.out" , "w" , stdout);
printf("%d\n" , nr );
vector<int>::iterator it;
for( int i = 1 ; i <= nr ; ++i )
{
sort(Comp[i].begin(),Comp[i].end());
Comp[i].erase(unique(Comp[i].begin(),Comp[i].end()),Comp[i].end());
for(it = Comp[i].begin() ; it < Comp[i].end() ; ++it)
printf("%d " , *it);
printf("\n");
}
}