Cod sursa(job #538441)

Utilizator dianadobrescuDobrescu Diana dianadobrescu Data 21 februarie 2011 13:52:02
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.08 kb
#include <fstream.h>

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

int Revista[100000][100000], teme, relatii, tema1, tema2, bun1, bun2, contor, i, j;

int main()
{
	fin >> teme >> relatii;
	for (i=1; i<=300; i++)
		Revista[0][i] =1;
	for (relatii; relatii >0; relatii--)
	{
		fin >> tema1 >> tema2;
		for (i=0; i<301; i++)
			if (Revista[i][tema1])
				bun1 =i;
		for (i=0; i<301; i++)
			if (Revista[i][tema2])
				bun2 =i;
		if (!bun1 && !bun2)
		{
			for (i=1; Revista[i][0]; i++) {}
			Revista[i][0] =1;
			Revista[i][tema1] =1;
			Revista[i][tema2] =1;
		}
		if (bun1 && !bun2)
			Revista[bun1][tema2] =1;
		if (!bun1 && bun2)
			Revista[bun2][tema1] =1;
		if (bun1 && bun2 && bun1!=bun2)
		{
			Revista[bun2][0] =0;
			for (i=1; i<301; i++)
				if (Revista[bun2][i])
				{
					Revista[bun2][i] =0;
					Revista[bun1][i] =1;
				}
		}
	}
	for (i=1; i<301; i++)
		if (Revista[i][0])
			contor++;
	for (i=1; i<=teme; i++)
	{
		for (j=0; j<301; j++)
			if (Revista[j][i])
				bun1 =j;
		if (!bun1)
			contor++;
	}
	fout << contor;
	return 0;
}