Pagini recente » Cod sursa (job #3244085) | Cod sursa (job #2657155) | Cod sursa (job #350547) | Cod sursa (job #1399735) | Cod sursa (job #1033225)
#include<cstdio>
#include<vector>
#include<utility>
#include<stack>
#include<algorithm>
#include<cmath>
#define N_MAX 100010
#define f first
#define s second
#define pb push_back
using namespace std;
stack <pair <int,int> > Q;
vector <int> G[N_MAX];
vector <int> cop;
vector <vector <int> > Sol;
bool pus[N_MAX];
int T[N_MAX],low[N_MAX],niv[N_MAX],a[N_MAX];
int N,NR;
inline void ins(int x,int niv)
{
if (a[x]==niv) return;
cop.pb(x);
a[x]=niv;
}
inline void DF(int x,int n)
{
vector <int> :: iterator it;
int y;
low[x]=n;
niv[x]=n;
pus[x]=true;
for (it=G[x].begin();it!=G[x].end();++it)
{
y=*it;
if (!pus[y])
{
pus[y]=true;
T[y]=x;
Q.push(make_pair(x,y));
DF(y,n+1);
NR++;
low[x]=min(low[x],low[y]);
if (low[y]>=niv[x])
{
//AM GASIT PCT DE ART => AVEM COMPONENTA BICONEXA
cop.clear();
int a,b;
do
{
a=Q.top().f;
b=Q.top().s;
Q.pop();
ins(a,NR);
ins(b,NR);
}
while (a!=x && b!=T[x]);
Sol.pb(cop);
}
}
else
{
if (y!=T[x]) low[x]=min(low[x],niv[y]);
}
}
}
inline void Load_Data()
{
int i,x,y,M;
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++)
pus[i]=false;
}
inline void Write_Data()
{
int i;
vector <int> :: iterator it;
printf("%d\n",Sol.size());
for (i=0;i<Sol.size();++i)
{
for (it=Sol[i].begin();it!=Sol[i].end();++it)
printf("%d ",*it);
printf("\n");
}
return;
}
int main()
{
int i;
freopen("biconex.in","r",stdin);
freopen("biconex.out","w",stdout);
Load_Data();
for (i=1;i<=N;i++)
if (!pus[i])
{
DF(i,1);
}
Write_Data();
fclose(stdin);
fclose(stdout);
return 0;
}