Pagini recente » Cod sursa (job #391870) | Cod sursa (job #39183) | Cod sursa (job #470691) | Cod sursa (job #2769356) | Cod sursa (job #627482)
Cod sursa(job #627482)
#include <queue>
#include <stack>
#include<stdio.h>
using namespace std;
int n,m,v[100000],nrdf[100000];
vector<int> l[100000];
int c,ndf,pozc=0;;
struct Muchie{
int i,j;
} ;
stack<Muchie> s;
vector<int> comp;
void bloc(int x,int tata){
Muchie m,mij;
ndf++;
nrdf[x]=ndf;
v[x]=ndf;
for(int t=0;t<l[x].size();t++){
int j=l[x][t];
if(nrdf[j]==0){
mij.i=x;
mij.j=j;
s.push(mij);
bloc(j,x);
if(v[j]>=nrdf[x]){
do{
m=s.top();
s.pop();
printf("%d %d",m.i,m.j);
comp.push_back(m.j);
}while(m.i!=mij.i || m.j!=mij.j );
comp.push_back(m.i);
comp.push_back(-1);
c++;
}
if(v[x]>v[j])
v[x]=v[j];
}
else
if(j!=tata){
if(v[x]>nrdf[j])
v[x]=nrdf[j];
}
}
}
void bloc(){
int i;
c=0;
for(i=0;i<n;i++){
v[i]=0;
nrdf[i]=0;
}
for(i=0;i<n;i++)
if(nrdf[i]==0)
bloc(i,-1);
}
int main(){
FILE *f;
int i,x,y,nrc=0,j;
f=fopen("biconex.in","r");
fscanf(f,"%d %d",&n,&m);
for(i=0;i<m;i++){
fscanf(f,"%d %d",&x,&y);
l[x-1].push_back(y-1);
l[y-1].push_back(x-1);
}
fclose(f);
bloc();
f=fopen("biconex.out","w");
fprintf(f,"%d",c);
fprintf(f,"\n",c);
for(j=0;j<comp.size();j++){
if(comp[j]>=0)
fprintf(f,"%d ",comp[j]+1);
else
fprintf(f,"\n");
}
fclose(f);
return 0;
}