Cod sursa(job #717134)

Utilizator halianStefanca Stefan halian Data 19 martie 2012 18:07:59
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.29 kb
#include <stdio.h>
#include <vector>
using namespace std;
#define FI fopen("ctc.in","r")
#define FO fopen("ctc.out","w")

vector<long> nod[100001],sol[100001];
long n,st[100000],nr,h[100001],stSize,nrSol,val[100001];
char inSol[100001];

void citeste(FILE *f) {
	long m,i,a,b;
	fscanf(f,"%li%li",&n,&m);
	for(i=0;i<m;i++) {
		fscanf(f,"%li%li",&a,&b);
		nod[a].push_back(b);
	}
}

void emptySt(long poz) {
	long i;
	for(i=poz;i<=stSize;i++) {
		sol[nrSol].push_back(st[i]);
		inSol[st[i]]=1;
	}
	nrSol++;
	stSize=poz-1;
}

long tarjan(long nodA,long poz,long niv) {
	long lim=nod[nodA].size(),i,x;
	st[poz]=nodA;
	h[nodA]=niv;
	val[nodA]=niv;
	stSize=poz;
	for(i=0;i<lim;i++)
		if(val[nod[nodA][i]] && val[nod[nodA][i]]<val[nodA])
			val[nodA]=val[nod[nodA][i]];
		else
			if(inSol[nod[nodA][i]]==0) {
				x=tarjan(nod[nodA][i],stSize+1,niv+1);
				if(x<val[nodA])
					val[nodA]=x;
			}
	if(val[nodA]==h[nodA])
		emptySt(poz);
	return val[nodA];
}

void scrie(FILE *f) {
	int i,j,lim;
	fprintf(f,"%li\n",nrSol);
	for(i=0;i<nrSol;i++) {
		lim=sol[i].size();
		for(j=0;j<lim;j++)
			fprintf(f,"%li ",sol[i][j]);
		fprintf(f,"\n");
	}
}

int main() {
	long i;
	citeste(FI);
	for(i=1;i<=n;i++)
		if(inSol[i]==0)
			tarjan(i,0,1);
	scrie(FO);
	return 0;
}