Cod sursa(job #362004)

Utilizator Ionescu_MariaIonescu Maria-Dorina Ionescu_Maria Data 7 noiembrie 2009 16:14:53
Problema Componente tare conexe Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 0.87 kb
#include<fstream>
#define nmax 10002
using namespace std;
int n,a[nmax][nmax],s[nmax],p[nmax],k;
//s[i]=p[i]=k => nodul i apartine celei de-a k-a componenta conexa
void cit()
{
	ifstream fin("ctc.in");
	int m,i,j;
	fin>>n>>m;
	while(m--)
	{
		fin>>i>>j;
		a[i][j]=1;
	}
	fin.close();
}
void ads(int i)
{
	s[i]=k;
	for(int j=1;j<=n;j++)
		if(s[j]==0&&a[i][j]==1)
			ads(j);
}
void adp(int i)
{
	p[i]=k;
	for(int j=1;j<=n;j++)
		if(p[j]==0&&a[j][i]==1)
			adp(j);
}
void actualizare()
{
	int i;
	for(i=1;i<=n;i++)
		if(p[i]==0||s[i]==0)
			p[i]=s[i]=0;
}
int main()
{
	int i,j;
	cit();
	k=0;
	for(i=1;i<=n;i++)
		if(s[i]==0)
		{
			k++;
			adp(i);
			ads(i);
			actualizare();
		}
	ofstream fout("ctc.out");
	fout<<k<<'\n';
	for(i=1;i<=k;i++)
	{
		for(j=1;j<=n;j++)
			if(s[j]==i)
				fout<<j<<" ";
		fout<<'\n';
	}
	return 0;
}