Cod sursa(job #411561)

Utilizator georgelRector George georgel Data 4 martie 2010 23:13:43
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.95 kb
#include<fstream>
#define Max 100001

using namespace std;

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

int a[Max][Max],m,n,nrc,suc[Max],pred[Max];
void read()
{
	int i,x,y;
	fin>>n>>m;
	for(i = 1; i <= m; i++)
	{
		fin>>x>>y;
		a[x][y] = 1;
	}
fin.close();
}

void df(int k)
{
	int i;
	suc[k] = nrc;
	for(i = 1; i <= n; i++)
		if(a[k][i] == 1 && suc[i] == 0)
			df(i);
}
void df2(int k)
{
	int i;
	pred[k] = nrc;
	for(i = 1; i <= n; i++)
		if(a[i][k] == 1 && pred[i] == 0)
			df2(i);
}			
int main()
{
	int i,j;
	read();
	nrc = 1;
	for(i = 1; i <= n; i++)
	{
		if(suc[i] == 0)
		{
			suc[i] = nrc;
			df(i);
			df2(i);
		for(j = 1; j <= n; j++)
			if(suc[j] != pred[j])
			suc[j] = pred[j] = 0;
			nrc++;
		}
	}
	fout<<nrc-1<<"\n";
int nr = 1;
for(i = 1; i <= nrc; i++)
{
	for(j = 1; j <= n; j++)
		if(suc[j] == nr)
		fout<<j<<" ";
		fout<<"\n";
nr = nr+1;	
}
fout.close();

return 0;

}