Pagini recente » Cod sursa (job #2634157) | Profil dragonking3499 | Cod sursa (job #1341333) | Cod sursa (job #2836175) | Cod sursa (job #426170)
Cod sursa(job #426170)
#include<stdio.h>
#include<stdlib.h>
using namespace std;
#define FIN "biconex.in"
#define FOUT "biconex.out"
#define NMAX 100004
#include<vector>
vector<int> g[NMAX];
int n,m;
struct Stiva{int x,y;Stiva *next;};
typedef Stiva* st;
void push(st &q,int x,int y)
{
st p=new Stiva;
p->x=x;
p->y=y;
p->next=q;
q=p;
}
void pop(st &q)
{
st p;
p=q;
q=q->next;
delete p;
}
st stack;
vector < vector < int > > rez;
int nivel[NMAX],low[NMAX];
inline void dfs(int nod,int tata,int nv)
{
nivel[nod]=low[nod]=nv;
vector<int>::iterator it;
for(it=g[nod].begin();it!=g[nod].end();it++)
{
if(*it==tata) continue;
if(nivel[*it]==-1) {push(stack,nod,*it);
dfs(*it,nod,nv+1);
low[nod]=min(low[*it],low[nod]);
if(low[*it]>=nivel[nod])
{
vector<int> aux;
int tx;int ty;
do
{tx=stack->x;
ty=stack->y;
aux.push_back(tx);aux.push_back(ty);
pop(stack);
}while(tx!=nod || ty!=*it);
rez.push_back(aux);
}
}
else low[nod]=min(low[nod],nivel[*it]);
}
}
int viz[NMAX];
int main()
{stack=new Stiva;
freopen(FIN,"r",stdin);
freopen(FOUT,"w",stdout);
scanf("%d %d",&n,&m);
for(int i=1;i<=m;i++)
{int x,y;
scanf("%d %d",&x,&y);
g[x].push_back(y);
g[y].push_back(x);
}
for(int i=1;i<=n;i++) nivel[i]=-1;
while(stack) pop(stack);
dfs(1,0,0);
printf("%d\n",rez.size());
for(int i=0;i<rez.size();i++)
{for(int j=0;j<rez[i].size();j++)
if(viz[rez[i][j]]==0) viz[rez[i][j]]=1,printf("%d ",rez[i][j]);
for(int j=0;j<rez[i].size();j++)
viz[rez[i][j]]=0;
printf("\n");
}
return 0;}