Cod sursa(job #573879)

Utilizator valibzValentin Ilie valibz Data 6 aprilie 2011 17:17:44
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.36 kb
#include <iostream>
#include <vector>
#include <stack>
#include <fstream>

#define DIM 31337

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

int indexx=1;
int ctc,k;
int x,y,i;
nod* v[DIM];
nod* solutie[DIM];
int s[DIM],idx[DIM],val[DIM],vizitat[DIM];

void adauga(int i,int j,nod *v[])
{
	nod *p;
	p=new nod;
	p->val=i;
	p->urm=v[i];
	v[i]=p;
}

void tarzan(int i,int n,int m)
{
	nod *p;
	vizitat[i]=1;
	idx[i]=indexx;
	val[i]=indexx;
	indexx++;
	s[++k]=i;
	
	// Consider successors of v

	for(p=v[i];p!=NULL;p=p->urm){
		if(!idx[p->val]){ 
			tarzan(p->val,n,m);
			if(val[i]>val[p->val])   
				val[i]=val[p->val];
		}else{ 
		    if(vizitat[p->val])
			if(val[i]>val[p->val])   
			    val[i]=val[p->val];
		}
	}
	if( idx[i] == val[i] ){ 
		int node;  
		ctc++;
		while( node!=i ){
			node=s[k];
			vizitat[node]=0;
			adauga(ctc,node,solutie);
			k--;
	      }
	}
}

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

	for(i=1;i<=ctc;i++)
	{ 
		while(solutie[i])
		{
			g<<solutie[i]->val<<" ";
			solutie[i]=solutie[i]->urm;
		}
			g<<'\n';
		}  
    g.close();
	return 0;
}