Cod sursa(job #566416)

Utilizator tudorsTudor Siminic tudors Data 28 martie 2011 22:42:13
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.44 kb
#include <stdio.h>
#include <vector>
#include <stack>
#define N 100001
#define INF 1<<31
using namespace std;

int n,m,nr,rez;
int index[N],L[N];
bool VIZ[N];
vector <int> A[N],R[N];
stack <int> S;
FILE *f, *g;

int minim(int a, int b)
{
	if (a<=b)
		return a;
	else
		return b;
}

void citire()
{
	int i,x,y;
	fscanf(f,"%d %d",&n,&m);
	for (i=1;i<=m;++i)
	{
		fscanf(f,"%d %d",&x,&y);
		A[x].push_back(y);
	}
}

void comp_strong(int nod)
{
	vector <int> :: iterator it;
	int v;
	index[nod]=L[nod]=nr++;
	VIZ[nod]=1;
	S.push(nod);
	for (it=A[nod].begin();it!=A[nod].end();it++)
		if (index[*it]==INF)
		{
			comp_strong(*it);
			L[nod]=minim(L[nod],L[*it]);
		}
		else if (VIZ[*it]==1)
			L[nod]=minim(L[nod],index[*it]);
	if (index[nod]==L[nod])
	{
		v=S.top();
		S.pop();
		VIZ[v]=0;
		rez++;
		R[rez].push_back(v);
		while (v!=nod)
		{
			v=S.top();
			VIZ[v]=0;
			S.pop();
			R[rez].push_back(v);
		}
	}
}

void tarjan()
{
	int i;
	for (i=1;i<=n;++i)
		index[i]=L[i]=INF;
	for (i=1;i<=n;++i)
		if (index[i]==INF)
			comp_strong(i);
}

void afisare()
{
	int i;
	vector <int> :: iterator it;
	fprintf(g,"%d\n",rez);
	for (i=1;i<=rez;i++)
	{
		for (it=R[i].begin();it!=R[i].end();it++)
			fprintf(g,"%d ",*it);
		fprintf(g,"\n");
	}
}

int main()
{
	f=fopen("ctc.in","r");
	g=fopen("ctc.out","w");
	citire();
	tarjan();
	afisare();
	fclose(f);
	fclose(g);
	return 0;
}