Pagini recente » Statistici Ana Matei (ana12) | Cod sursa (job #2006244) | Cod sursa (job #1277072) | tema | Cod sursa (job #726717)
Cod sursa(job #726717)
#include<stdio.h>
#include<vector>
#include<stack>
#include<algorithm>
using namespace std;
stack < pair <int,int> > s;
vector <int> l[100005],c[100005];
int niv[100005],nivmin[100005],t[100005],n,m,nr;
void cit(){
FILE *f;
int i,a,b;
f=fopen("biconex.in","r");
fscanf(f,"%d%d",&n,&m);
for(i=1;i<=m;i++){
fscanf(f,"%d%d",&a,&b);
l[a].push_back(b);
l[b].push_back(a);
}
fclose(f);
}
void comp_biconexa(int a,int b){
int x,y;
nr++;
do{
x=s.top().first;
y=s.top().second;
s.pop();
c[nr].push_back(x);
c[nr].push_back(y);
}while(x!=a||y!=b);
}
void df(int k){
nivmin[k]=niv[k];
for(unsigned int i=0;i<l[k].size();i++)
if(niv[l[k][i]]==0){
niv[l[k][i]]=niv[k]+1;
t[l[k][i]]=k;
s.push(make_pair(k,l[k][i]));
df(l[k][i]);
if(nivmin[l[k][i]]<nivmin[k])
nivmin[k]=nivmin[l[k][i]];
if(nivmin[l[k][i]]>=niv[k])
comp_biconexa(k,l[k][i]);
}else
if(l[k][i]!=t[k])
if(niv[l[k][i]]<nivmin[k]){
s.push(make_pair(k,l[k][i]));
nivmin[k]=niv[l[k][i]];
}
}
void afis(){
int i;
FILE *f;
f=fopen("biconex.out","w");
fprintf(f,"%d\n",nr);
for(i=1;i<=nr;i++){
sort(c[i].begin(),c[i].end());
c[i].erase(unique(c[i].begin(),c[i].end()),c[i].end());
for(unsigned int j=0;j<c[i].size();j++)
fprintf(f,"%d ",c[i][j]);
fprintf(f,"\n");
}
fclose(f);
}
int main(){
cit();
niv[1]=1;
df(1);
afis();
return 0;
}