Pagini recente » Cod sursa (job #2817794) | Cod sursa (job #1437715) | Cod sursa (job #850460) | Cod sursa (job #1189713) | Cod sursa (job #1119929)
#include<cstdio>
#include<vector>
#include<stack>
using namespace std;
#define MAX 100001
#define pb push_back
#define mp make_pair
#define PII pair<int,int>
#define x first
#define y second
int N , M , k , niv[MAX] , low[MAX] , t[MAX] , viz[MAX];
vector<int> G[MAX] , Comp[MAX];
stack<PII> st;
void read();
void solve();
void write();
void DF(int nod);
void Make_comp(int k , int x , int y);
int main()
{
read();
solve();
write();
return 0;
}
void read()
{
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(!niv[i])
{
niv[i] = 1;
DF(i);
}
}
void DF(int nod)
{
low[nod] = niv[nod];
for(int i = 0 ; i< (int)G[nod].size() ; ++i )
{
if(!niv[G[nod][i]])
{
t[G[nod][i]] = nod;
niv[G[nod][i]] = niv[nod] +1;
st.push(mp(nod,G[nod][i]));
DF(G[nod][i]);
if(low[G[nod][i]] < low[nod])
low[nod] = low[G[nod][i]];
if(low[G[nod][i]] >= niv[nod])
Make_comp(++k,nod,G[nod][i]);
}
else
if(G[nod][i] != t[nod] && low[G[nod][i]] < low[nod])
low[nod] = low[G[nod][i]];
}
}
void Make_comp(int k , int x , int y)
{
PII m;
do
{
m = st.top();
st.pop();
if(viz[m.x] != k)
{
viz[m.x] = k;
Comp[k].pb(m.x);
}
if(viz[m.y] != k)
{
viz[m.y] = k;
Comp[k].pb(m.y);
}
}while(m.x != x && m.y != y);
}
void write()
{
freopen("biconex.out" , "w" , stdout );
printf("%d\n" , k);
for(int i = 1 ; i <= k ; ++i )
{
for(int j = 0 ; j <(int)Comp[i].size() ; ++j )
printf("%d " , Comp[i][j]);
printf("\n");
}
}