Pagini recente » Cod sursa (job #3181587) | Cod sursa (job #1585335) | Cod sursa (job #3198424) | Cod sursa (job #955612) | Cod sursa (job #2189514)
#include<stdio.h>
#include<algorithm>
#include<vector>
#define MAXV 100000
#define MAXE 500000
void dfs(int nod);
FILE*fin,*fout;
int lista[MAXV+1],next[MAXE+1],val[MAXE+1],k=0;
int st[MAXE+1],ult=-1;
std::pair<int,int> edge[MAXE+1];
std::vector<std::vector<int>> sol;
std::vector<int> partial_sol;
int level[MAXV+1],ind[MAXV+1];
int tata[MAXV+1];
int index=0;
int main()
{
fin=fopen("biconex.in","r");
fout=fopen("biconex.out","w");
int V,E;
fscanf(fin,"%d%d",&V,&E);
for(int i=1; i<=E; i++)
{
int x,y;
fscanf(fin,"%d%d",&x,&y);
next[++k]=lista[y];
val[k]=x;
lista[y]=k;
next[++k]=lista[x];
val[k]=y;
lista[x]=k;
}
/*for(int i=1;i<=V;i++)
{
if(ind[i]==0)
{
dfs(i);
}
}*/
dfs(1);
fprintf(fout,"%d\n",sol.size());
for(int i=0;i<sol.size();i++)
{
for(int j=0;j<sol[i].size();j++)
{
fprintf(fout,"%d ",sol[i][j]);
}
fprintf(fout,"\n");
}
/*fprintf(fout, "\n\n\n\n\n-----------\n");
for(int i = 1; i <= V; i++)
fprintf(fout, "%d ", level[i]);*/
fclose(fin);
fclose(fout);
}
void dfs(int nod)
{
ind[nod]= ind[tata[nod]] + 1;
level[nod]=ind[nod];
int p=lista[nod];
while(p!=0)
{
int vec=val[p];
if(tata[nod] != vec){
if(ind[vec]==0)
{
st[++ult]=p;
tata[vec]=nod;
dfs(vec);
level[nod]=std::min(level[nod],level[vec]);
if(ind[nod]<=level[vec])
{
partial_sol.resize(0);
while(ult>0 && st[ult]!=p)
{
partial_sol.push_back(val[st[ult]]);
//printf("%d ",val[st[ult]]);
ult--;
}
partial_sol.push_back(val[p]);
//printf("%d ",val[p]);
ult--;
partial_sol.push_back(nod);
//printf("%d\n",nod);
sol.push_back(partial_sol);
}
}
else
{
level[nod]=std::min(level[nod],ind[vec]);
}
}
p=next[p];
}
}