Cod sursa(job #573891)

Utilizator valibzValentin Ilie valibz Data 6 aprilie 2011 17:27:38
Problema Componente tare conexe Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.29 kb
#include<iostream>
#include<fstream>

#define DIM 31337

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

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


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

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

	for(p=v[i];p!=NULL;p=p->next){
		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;
			adauga(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; 
	      adauga(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++){ 
	for(i=1;i<=ctc;i++){ 
	  
	while(sol[i]){
		g<<sol[i]->x<<" ";
		sol[i]=sol[i]->next;
	}
		g<<'\n';
	}
	}
      
    g.close();
	return 0;
}