Cod sursa(job #627482)

Utilizator Mirc100Mircea Octavian Mirc100 Data 30 octombrie 2011 01:24:22
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.71 kb
#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;   
}