Cod sursa(job #775498)

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

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

void df1(int v)
{
	vector <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)
{
	vector <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].push_back(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].push_back(v2);
		GT[v2].push_back(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;
	for (i=n;i>=1;i--)
		if (VIZ[S[i]]==0)
		{
			nrc++;
			df2(S[i]);
		}
	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;
}