Cod sursa(job #573222)

Utilizator keller946Radoi Liviu keller946 Data 6 aprilie 2011 01:45:47
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.15 kb
#include<fstream>

#define SIZE 100010

typedef struct nod { 
      int x; 
      nod *urm;
  
}nod;

nod *v[SIZE],*sol[SIZE];

int indx=1;
int ctc,k,n,m,x,y,i;
int s[SIZE],indice[SIZE],val[SIZE],vizitat[SIZE];


void add(int i, int j,nod *v[]){ nod *p;
    p=new nod;
    p->x=j;
    p->urm=v[i];
    v[i]=p;
}
void tarjan (int i){ 
	nod *p;
	vizitat[i]=1;
	indice[i]=indx;
	val[i]=indx;
	indx++;
	s[++k]=i;

	for(p=v[i];p!=NULL;p=p->urm){
		if(!indice[p->x]){ 
			tarjan(p->x);
			if(val[i]>val[p->x])   
				val[i]=val[p->x];
		}else{ 
		    if(vizitat[p->x])
			if(val[i]>val[p->x])   
			    val[i]=val[p->x];
		}
	}

	if( indice[i] == val[i] ){ 
		int node;  
		ctc++;
		while( node!=i ){
			node=s[k];
			vizitat[node]=0;
			add(ctc,node,sol);
			k--;
	      }
	
	}
}


int main(int argc, char **argv){
    
    std::ifstream f("ctc.in");
    	f>>n>>m;
	for(i=1;i<=m;i++){ 
	      f>>x>>y; 
	      add(x,y,v);
	}
	f.close();
	
	for(i=1;i<=n;i++)
		if(!indice[i]) 
			tarjan(i);
	
	std::ofstream g("ctc.out");
	  g<<ctc<<'\n';

	for(i=1;i<=ctc;i++){ 
	  
	  while(sol[i]){
		g<<sol[i]->x<<" ";
		sol[i]=sol[i]->urm;
	  }
		g<<'\n';
	}

      
      g.close();
return 0;
}