Pagini recente » Borderou de evaluare (job #2470243) | Cod sursa (job #3002781) | Borderou de evaluare (job #804947) | Borderou de evaluare (job #2113669) | Cod sursa (job #627471)
Cod sursa(job #627471)
#include <queue>
#include <stack>
#include<stdio.h>
using namespace std;
int n,m,viz[100000],v[100000],tata[100000],nrdf[100000];
vector<int> l[100000];
int c,ndf;
struct Muchie{
int i,j;
} ;
stack<Muchie> s;
stack<int> comp[200001];
void dfs(int x){
viz[x]=1;
for(int i=0;i<l[x].size();i++)
if (viz[l[x][i]]==0)
dfs(l[x][i]);
}
void bloc(int x){
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);
tata[j]=x;
bloc(j);
if(v[j]>=nrdf[x]){
do{
m=s.top();
s.pop();
comp[c].push(m.j);
}while(m.i!=mij.i || m.j!=mij.j );
comp[c].push(mij.i);
c++;
}
if(v[x]>v[j])
v[x]=v[j];
}
else
if(j!=tata[x]){
if(v[x]>nrdf[j])
v[x]=nrdf[j];
}
}
}
void bloc(){
int i;
c=0;
for(i=0;i<n;i++){
v[i]=0;
tata[i]=0;
nrdf[i]=0;
}
for(i=0;i<n;i++)
if(nrdf[i]==0)
bloc(i);
}
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);
for(i=0;i<c;i++){
fprintf(f,"\n",c);
while(comp[i].size()>0){
fprintf(f,"%d ",comp[i].top()+1);
comp[i].pop();
}
}
fclose(f);
return 0;
}