Cod sursa(job #1337552)

Utilizator dica69Alexandru Lincan dica69 Data 9 februarie 2015 10:44:00
Problema Componente biconexe Scor 52
Compilator cpp Status done
Runda Arhiva educationala Marime 1.4 kb
#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.