Cod sursa(job #799877)

Utilizator roots4Irimia Alexandru Gabriel roots4 Data 20 octombrie 2012 11:58:57
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.15 kb
#include<stdio.h>
#define dim 100010
#include<vector>
#include<algorithm>
using namespace std;
int viz[dim],low[dim],next,i,j,n,m,nr,a,b,stiva[dim],ctc;

vector <int> P[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]){
		int v;
		ctc++;
		do {
			v = stiva[stiva[0]--];
			viz[v] = - viz[v];
			P[ctc].push_back(v);
		} while (v!=x);
	}
}


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