Cod sursa(job #1250398)

Utilizator casuneanu.andreiCasuneanu Andrei Dan casuneanu.andrei Data 28 octombrie 2014 06:39:16
Problema Componente tare conexe Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.01 kb
#include <fstream>
#define IN "ctc.in"
#define OUT "ctc.out"
#define DMAX 1000
using namespace std;

ifstream fin(IN);
ofstream fout(OUT);

//matricea d
int d[DMAX][DMAX];
int use[DMAX];
int n, m;
int nrt;

void citire();
void afisare();
void constr_d();
void showtime();

int main(int argc, const char * argv[])
{
	citire();
	constr_d();
	showtime();
	afisare();
    return 0;
}

void afisare()
{
	int i, j;
	fout <<nrt<<'\n';
	for (i=1; i<=nrt; ++i)
	{
		for (j=1; j<=n; ++j)
			if (use[j]==i)
				fout <<j<<' ';
		fout <<'\n';
	}
}

void showtime()
{
	int x, y, bun;
	for (x=1; x<=n; ++x)
	{
		for (y=1, bun=0; y<=n; ++y)
			if (d[x][y]==d[y][x] && d[y][x]==1 && !use[y])
			{use[y]=nrt+1; bun=1;}
		//daca e izolat nu e bene
		nrt+=bun;
	}
}

void constr_d()
{
	int i, j, k;
	for (k=1; k<=n; ++k)
		for (i=1; i<=n; ++i)
			for (j=1; j<=n; ++j)
				if (!d[i][j])
					d[i][j]=d[i][k]&&d[k][j];
}

void citire()
{
	fin >>n>>m;
	
	int i, x, y;
	for (i=0; i<m; ++i)
	{
		fin >>x>>y;
		d[x][y]=1;
	}
	for (i=1; i<=n; ++i)
		d[i][i]=1;
}