Pagini recente » Cod sursa (job #3191460) | Cod sursa (job #2178547) | Cod sursa (job #3433) | Cod sursa (job #679064) | Cod sursa (job #1028824)
#include<cstdio>
#include<list>
#include<vector>
#include<utility>
#include<stack>
#define f first
#define s second
#define N_MAX 100010
#define M_MAX 200010
#define pb push_back
using namespace std;
stack < pair <int,int> > Q;
vector <int> G[N_MAX];
vector < vector <int> > sol;
vector<int> cop;
bool fol[N_MAX];
int niv[N_MAX],low[N_MAX],T[N_MAX],Val[N_MAX];
int N,nr;
inline void Insert(int x,int niv)
{
if (Val[x]==niv) return;
Val[x]=niv;
cop.pb(x);
}
//parcurgere DF
inline void DF(int x,int n)
{
int y=0,a,b;
vector <int> :: iterator it;
niv[x]=n;
low[x]=n;
for (it=G[x].begin();it!=G[x].end();++it)
if (!fol[*it])
{
fol[*it]=true;
T[*it]=x;
Q.push(make_pair(x,*it));
DF(*it,n+1);
y=*it;
nr++;
if (low[x]>low[y]) low[x]=low[y];
if (low[y]>=niv[x])
{
//X E PCT DE ARTICULATIE =>AM GASIT O COMPONENTA BICONEXA
int a,b;
cop.clear();
do
{
a=Q.top().f;
b=Q.top().s;
Q.pop();
Insert(a,nr);
Insert(b,nr);
}
while (a!=x && b!=T[x]);
sol.pb(cop);
}
}
else
{
y=*it;
if (y!=T[x] && low[x]>niv[y])
low[x]=niv[y];
}
}
//citire
inline void Load_Data()
{
int M,i,x,y;
scanf("%d%d",&N,&M);
for (i=1;i<=M;i++)
{
scanf("%d%d",&x,&y);
G[x].pb(y);
G[y].pb(x);
}
for (i=1;i<=N;i++)
fol[i]=false;
}
inline void Write_Data()
{
int i,j;
printf("%d",sol.size());
for (i=0;i<sol.size();++i)
{
printf("\n");
for (j=0;j<sol[i].size();++j)
printf("%d ",sol[i][j]);
}
}
int main()
{
freopen("biconex.in","r",stdin);
freopen("biconex.out","w",stdout);
Load_Data();
for (int i=1;i<=N;i++)
if (!fol[i]) DF(i,1);
Write_Data();
fclose(stdin);
fclose(stdout);
return 0;
}