Cod sursa(job #799870)

Utilizator roots4Irimia Alexandru Gabriel roots4 Data 20 octombrie 2012 11:50:36
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.14 kb
#include<stdio.h>
#define dim 100010

int viz[dim],low[dim],next,i,j,n,m,nr,a,b,stiva[dim],R[100][dim];

FILE*f=fopen("ctc.in","r");
FILE*g=fopen("ctc.out","w");

struct nod{
	int nr;
	nod *adr;
}*p,*L[dim];

void read(){
	fscanf(f,"%d%d",&n,&m);
	for(i=1;i<=m;i++){
		fscanf(f,"%d%d",&a,&b);
		p=new nod;
		p->nr=b;
		p->adr=L[a];
		L[a]=p;
	}
}

int min(int a,int b){
	if(a<b)
		return a;
	return b;
}

void dfs(int x){
	next++;
	viz[x]=next;
	low[x]=next;
	stiva[++stiva[0]]=x;
	nod *c;
	for(c=L[x];c!=0;c=c->adr){
		if(!viz[c->nr]){
			dfs(c->nr);
			low[x]=min(low[x],low[c->nr]);
		}
		else{
			if(viz[c->nr]>0)
				low[x]=min(low[x],low[c->nr]);
		}
	}
	if(viz[x]==low[x]){
		nr++;
		do{
			R[nr][++R[nr][0]]=stiva[stiva[0]];
			viz[stiva[stiva[0]]]*=(-1);
			stiva[0]--;
		}while(stiva[stiva[0]]!=x);
		R[nr][++R[nr][0]]=stiva[stiva[0]];
		stiva[0]--;
	}
}


int main(){
	
	read();
	
	
	for(i=1;i<=n;i++){
		if(!viz[i]){
			dfs(i);
		}
	}
	
	fprintf(g,"%d\n",nr);
	
	for(i=1;i<=nr;i++){
		for(j=1;j<=R[i][0];j++)
			fprintf(g,"%d ",R[i][j]);
		fprintf(g,"\n");
	}
	
	return 0;
}