Cod sursa(job #653206)

Utilizator informatician28Andrei Dinu informatician28 Data 27 decembrie 2011 16:32:13
Problema Componente tare conexe Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 0.89 kb
#include<fstream> 
using namespace std; 

ifstream in("ctc.in"); 
ofstream out("ctc.out");

int N,M,A[250][250],nrc=1,suc[100001],pred[100001];
void Read() 
{
	int x,y,i;
	in>>N>>M; 
	for(i = 1; i <= M; ++ i)
		{
			in >> x >> y;
			A[x][y]=1; 
	}
}

void df_1(int nod) 
{
	int i;
	suc[nod]=nrc; 
	for(i = 1; i <= N; ++ i) 
		if(A[nod][i]==1 && !suc[i]) 
			df_1(i); 
}

void df_2(int nod) 
{
	int i; 
	pred[nod]=nrc; 
	for(i = 1; i <=N; ++ i) 
		if(A[i][nod]==1 && !pred[i]) 
			df_2(i); 
}

int main() 
{
	int i,j;
	Read(); 
	
	for(i = 1; i <= N; ++ i) 
	
		if(!suc[i]) 
		{
			suc[i]=nrc;
			df_1(i); df_2(i); 
		for(j = 1; j <= N; j++) 
		if(suc[j]!=pred[j]) 
			suc[j]=pred[j]=0; 
		 nrc ++; 
		}
		
		out << nrc-1 << '\n'; 
		for(i = 1; i < nrc; ++i) 
			{
				for( j = 1; j <= N; ++j) 
				if(suc[j]==i) out << j << " "; 
				out << '\n'; 
		}
}