Pagini recente » Cod sursa (job #1681482) | Cod sursa (job #2839838) | Cod sursa (job #2724446) | Cod sursa (job #2981359) | Cod sursa (job #360415)
Cod sursa(job #360415)
#include <stdio.h>
#include <vector>
using namespace std;
vector<int> G[10000];
int Tata[10000], Lv[10000], Low[10000], Use[10000];
int Stiva[2][10000];
int i,n,m,x,y,j,Numar;
int Lungime;
vector< vector<int> > Comp;
void Nod_Critic(int nod, int fiu)
{
int x,y;
vector<int> c;
Numar++;
do{
x = Stiva[0][Lungime];
y = Stiva[1][Lungime--];
c.push_back(x); c.push_back(y);
}while (((x!=nod) || (y!=fiu)) && ((x!=fiu) || (y!=nod)));
Comp.push_back(c);
}
void DF_Biconex(int nod)
{
int i;
Use[nod]=1; Low[nod]=Lv[nod];
for (i=0; i<G[nod].size(); i++){
if ( (G[nod][i] != Tata[nod]) && (Lv[nod] > Lv[ G[nod][i] ]) ){
Stiva[0][++Lungime] = G[nod][i];
Stiva[1][Lungime] = nod;
}
if (!Use[ G[nod][i] ]){
Lv[ G[nod][i] ] = Lv[nod]+1;
Tata[ G[nod][i] ] = nod;
DF_Biconex( G[nod][i] );
if (Low[nod] > Low[ G[nod][i] ])
Low[nod] = Low[ G[nod][i] ];
if (Low[ G[nod][i] ] >= Lv[nod] )
Nod_Critic(nod, G[nod][i]);
}
else
if ( (G[nod][i]!=Tata[nod]) && (Low[nod] > Lv[ G[nod][i] ]))
Low[nod] = Lv[ G[nod][i] ];
}
}
int main()
{
freopen("biconex.in","r",stdin);
freopen("biconex.out","w",stdout);
scanf("%d %d",&n,&m);
for (i=1; i<=m; i++){
scanf("%d %d",&x,&y);
G[x].push_back(y);
G[y].push_back(x);
}
for (i=1; i<=n; i++)
if (!Use[i]){
Lv[i]=1;
DF_Biconex(i);
}
printf("%d\n",Numar);
for (i=0; i<Numar; i++){
printf("%d ",Comp[i][0]);
for (j=1; j+1<Comp[i].size(); j++)
if (Comp[i][j]!=Comp[i][j-1])
printf("%d ",Comp[i][j]);
if (Comp[i][j]!=Comp[i][0])
printf("%d\n",Comp[i][j]);
else
printf("\n");
}
return 0;
}