Cod sursa(job #653567)

Utilizator informatician28Andrei Dinu informatician28 Data 28 decembrie 2011 13:15:55
Problema Componente tare conexe Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 0.99 kb
#include<fstream> 
#include<vector>
using namespace std; 

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

int N,M,nrc=1,suc[100010],pred[100010];
vector<int>A[100010],At[100010];

void Read() 

{
	int x,y,i;
	in>>N>>M; 
	for(i = 1; i <= M; ++ i)
		{
			in >> x >> y;
			A[x].push_back(y); 
			At[y].push_back(x);
	}
}

void df_1(int nod) 
{
	int i;
	suc[nod]=nrc; 
	for(i = 0; i < A[nod].size(); ++ i) 
		if(!suc[A[nod][i]]) 
			df_1(A[nod][i]); 
}

void df_2(int nod) 
{
	int i; 
	pred[nod]=nrc; 
	for(i = 0; i < At[nod].size(); ++ i) 
		if(!pred[At[nod][i]]) 
			df_2(At[nod][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'; 
		}
}