Pagini recente » Cod sursa (job #2294735) | Cod sursa (job #2919168) | Cod sursa (job #1469215) | Cod sursa (job #2910826) | Cod sursa (job #1205106)
#include<fstream>
#include<vector>
#include<algorithm>
using namespace std;
ifstream f("biconex.in");
ofstream o("biconex.out");
vector <int> a[100100];
int m,n,l[100100],minim[100100],critic[100100],parc[100010];
void df(int nod,int tata,int v){
parc[nod]=1;
l[nod]=minim[nod]=v;
for(int i=0;i<a[nod].size();i++)
if(a[nod][i]!=tata){
if(parc[a[nod][i]]==1){
minim[nod] = min(minim[nod],l[a[nod][i]]);
}else{
df(a[nod][i],nod,v+1);
minim[nod] = min(minim[nod],minim[a[nod][i]]);
}
if(l[nod]<=minim[a[nod][i]]){
critic[nod]=1;
}
}
parc[nod]=0;
}
void df1(int nod){
parc[nod]=1;
int ok=1;
for(int i=0;i<a[nod].size();i++)
if(parc[a[nod][i]]!=1){
ok=0;
o<<nod<<" ";
if(critic[a[nod][i]]==1)o<<a[nod][i]<<"\n";
df1(a[nod][i]);
}
if(ok)o<<nod<<"\n";
// parc[nod]=0;
}
int nr(int nod){
parc[nod]=1;
int ok=1,sum = 0;
for(int i=0;i<a[nod].size();i++)
if(parc[a[nod][i]]!=1){
ok=0;
// o<<nod<<" ";
if(critic[a[nod][i]]==1)sum++;
sum += nr(a[nod][i]);
}
if(ok) return 1;
else return sum;
// parc[nod]=0;
}
int main(){
f>>n>>m;
int x,y;
for(int i=1;i<=m;i++){
f>>x>>y;
a[x].push_back(y);
a[y].push_back(x);
}
df(1,1,1);
//for(int i=1;i<=n;i++)
// if(critic[i]==1)o<<i<<endl;
o<<nr(1)<<"\n";
for(int i=1;i<=n;i++)parc[i]=0;
df1(1);
}