Cod sursa(job #552228)

Utilizator moonRadu Chichi moon Data 11 martie 2011 21:32:59
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.1 kb
#include<iostream>
#include<fstream>
using namespace std;
unsigned long n,s,m,a[10001][10001],a2[10001][10001],a3[10001][10001],viz[10001],nr,v[10001];
int main()
{
	unsigned long xx,yy,i,j,k;
	ifstream f("ctc.in");
	ofstream g("ctc.out");
	f>>n>>m;
	for(i=1;i<=m;i++)
	{
		f>>xx>>yy;
		a[xx][yy]=1;
		a2[yy][xx]=1;
	}
	
	for(k=1;k<=n;k++)
		for(i=1;i<=n;i++)
			for(j=1;j<=n;j++)
			{
				if(a[i][j]==0 && i!=j && i!=k && j!=k)
					a[i][j]=a[i][k]*a[k][j];
				if(a2[i][j]==0 && i!=j && i!=k && j!=k)
					a2[i][j]=a2[i][k]*a2[k][j];
			}
				
	
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=n;j++)
		{
			if(a[i][j] && a2[i][j])
				a3[i][j]=1;
		//	cout<<a3[i][j]<<" ";
		}	
		//	cout<<'\n';
	}
	
	nr=0;
	int nrt=0;
    for(i=1;i<=n;i++)
	{
		if(!viz[i])
		{
			nr++;
			v[nr]=i;
			//cout<<i<<" ";
			for(j=1;j<=n;j++)
				if(a3[i][j] && !viz[j])
					{
						//cout<<j<<" ";
						nr++;
						v[nr]=j;
						viz[j]=1;
					}
			nr++;
			nrt++;
			v[nr]=0;
			viz[i]=1;
		}
	}
	cout<<nrt<<'\n';
	for(i=1;i<=nr;i++)
		if(v[i]==0) cout<<'\n';
	     else cout<<v[i]<<" ";
}