Pagini recente » Cod sursa (job #548838) | Cod sursa (job #2841918) | Cod sursa (job #156528) | Cod sursa (job #2477868) | Cod sursa (job #1337576)
#include <iostream>
#include <cstdio>
#include <list>
#include <stack>
#include <utility>
#include <vector>
#include <cstring>
#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;
bool use[Nmax];
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++;
memset(use,0,sizeof(use));
do
{u=s.top().first;v=s.top().second;s.pop();
if (!use[u]) {sol[nr].push_back(u);use[u]=1;}
if (!use[v]) {sol[nr].push_back(v);use[v]=1;}
}
while (u!=x || v!=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.