Cod sursa(job #1205106)

Utilizator IonMosnoiIon Mosnoi IonMosnoi Data 5 iulie 2014 11:06:20
Problema Componente biconexe Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.48 kb
#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);
}