Cod sursa(job #775495)

Utilizator veleanduAlex Velea veleandu Data 8 august 2012 12:15:24
Problema Componente tare conexe Scor 36
Compilator cpp Status done
Runda Arhiva educationala Marime 1.21 kb
#include <stdio.h>
#include <set>
using namespace std;
FILE *fi,*fo;
int n,m;
int i,v1,v2,v;
set <int> G[100001];
set <int> GT[100001];
set <int> CTC[100001];
set <int> :: iterator it;
int nrc;

int S[100001],k;
int VIZ[100001];

void df1(int v)
{
	set <int> :: iterator it;
	int i;
	VIZ[v]=1;
	for (it=G[v].begin();it!=G[v].end();it++)
	{
		i=(*it);
		if (VIZ[i]==0)
			df1(i);
	}
	S[++k]=v;
}

void df2(int v)
{
	set <int> :: iterator it;
	int i;
	VIZ[v]=1;
	for (it=GT[v].begin();it!=GT[v].end();it++)
	{
		i=(*it);
		if (VIZ[i]==0)
			df2(i);
	}
	CTC[nrc].insert(v);
}

int main()
{
	fi=fopen("ctc.in","r");
	fo=fopen("ctc.out","w");
	fscanf(fi,"%d%d",&n,&m);
	for (i=1;i<=m;i++)
	{
		fscanf(fi,"%d%d",&v1,&v2);
		G[v1].insert(v2);
		GT[v2].insert(v1);
	}
	for (v=1;v<=n;v++)
		if (VIZ[v]==0)
			df1(v);
	nrc=0;
	/*for (i=1;i<=n;i++)
		fprintf(fo,"%d ",S[i]);*/
	for (i=1;i<=n;i++)
		VIZ[i]=0;
	k=n;
	while (k>0)
	{
		nrc++;
		df2(S[k]);
		k-=CTC[nrc].size();
	}
	fprintf(fo,"%d\n",nrc);
	for (i=1;i<=nrc;i++)
	{
		for (it=CTC[i].begin();it!=CTC[i].end();it++)
			fprintf(fo,"%d ",(*it));
		fprintf(fo,"\n");
	}
	fclose(fi);
	fclose(fo);
	return 0;
}