Pagini recente » Cod sursa (job #1500329) | Cod sursa (job #2669038) | Cod sursa (job #73453) | Cod sursa (job #1108458) | Cod sursa (job #1337552)
#include <iostream>
#include <cstdio>
#include <list>
#include <stack>
#include <utility>
#include <vector>
#define Nmax 100001
#define Mmax 200001
using namespace std;
FILE *f1,*f2;
int n,m,i,x,y,nv[Nmax],l[Nmax],nr,sn,num,j;
list <int> a[Nmax];
stack <pair <int,int> > s;
vector <int> sol[Nmax];
void Init()
{int i;
for (i=1;i<=n;i++) nv[i]=l[i]=-1;
s.push(make_pair(1,-1));
}
void solutie(int x,int y)
{int u,v;
nr++;
do
{u=s.top().first;v=s.top().second;s.pop();
sol[nr].push_back(u);
}
while (u!=x || v!=y);
if (y!=sol[nr][0]) sol[nr].push_back(y);
}
void Biconex(int nod,int t)
{int x;
list <int> ::iterator it;
nv[nod]=l[nod]=++num;
for (it=a[nod].begin();it!=a[nod].end();it++)
{x=*it;
if (x!=t && nv[x]<nv[nod]) s.push(make_pair(x,nod));
if (nv[x]==-1)
{Biconex(x,nod);
l[nod]=min(l[x],l[nod]);
if (l[x]>=nv[nod]) solutie(x,nod);
}
else
if (x!=t) l[nod]=min(l[nod],nv[x]); }
}
int main()
{f1 = fopen("biconex.in","r");
f2 = fopen("biconex.out","w");
fscanf(f1,"%d%d",&n,&m);
for (i=1;i<=m;i++) {fscanf(f1,"%d%d",&x,&y);a[x].push_back(y);a[y].push_back(x);}
Init();
Biconex(1,-1);
fprintf(f2,"%d\n",nr);
for (i=1;i<=nr;i++)
{for (j=0;j<(int)sol[i].size();j++) fprintf(f2,"%d ",sol[i][j]);
fprintf(f2,"\n");
}
fclose(f1);
fclose(f2);
return 0;
}
//Challenges are what make life interesting and overcoming them is what makes life meaningful.