Cod sursa(job #616096)

Utilizator maritimCristian Lambru maritim Data 11 octombrie 2011 18:41:34
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.08 kb
#include<stdio.h>
#include<vector>
using namespace std;

#define MaxN 100100

typedef vector<int>::iterator it;

vector<int> A[MaxN],B[MaxN],C[MaxN];
int N,M,nr,MAX,S[MaxN],viz[MaxN];

void citire(void)
{
	int a,b;
	FILE *f = fopen("ctc.in","r");
	
	fscanf(f,"%d %d ",&N,&M);
	for(int i=1;i<=M;i++)
	{
		fscanf(f,"%d %d",&a,&b);
		A[a].push_back(b);
		B[b].push_back(a);
	}
	
	fclose(f);
}

void DFBIS(int a)
{
	viz[a] = 1;
	for(it i=A[a].begin();i<A[a].end();i++)
		if(!viz[*i])
			DFBIS(*i);
	S[++nr] = a;
}

void DFAFIS(int a)
{
	C[MAX].push_back(a);
	viz[a] = 0;
	for(it i=B[a].begin();i<B[a].end();i++)
		if(viz[*i])
			DFAFIS(*i);
}

void kosaraju(void)
{
	for(int i=1;i<=N;i++)
		if(!viz[i])
			DFBIS(i);
	for(int i=N;i;i--)
		if(viz[S[i]])
			++MAX,DFAFIS(S[i]);
}

void Afis(void)
{
	FILE *g = fopen("ctc.out","w");
	
	fprintf(g,"%d\n",MAX);
	for(int i=1;i<=MAX;i++,fprintf(g,"\n"))
		for(it j=C[i].begin();j<C[i].end();j++)
			fprintf(g,"%d ",*j);
	
	fclose(g);
}

int main()
{
	citire();
	kosaraju();
	Afis();
	return 0;
}