Cod sursa(job #451414)

Utilizator emilia.ciobanuCiobanu Emilia Maria Silvia emilia.ciobanu Data 9 mai 2010 15:23:00
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.18 kb
#include<fstream>
#include<vector>
#include<list>

#define IN "dfs.in"
#define OUT "dfs.out"
#define INF ~(1<<31)
#define NIL -1
#define ALB 0
#define GRI 1
#define NEGRU 2

using namespace std;

vector<list<int> >L;
int N, M;
vector <int> P;
vector <int> REZ;
vector <int> C, S, F;
int t, nr;

void read (char *);
void DFS ();
void DFSV (int);


int main(int argc, char **argv)
{
	read (argv[1]);
	DFS();

	int i;

	FILE *fout = fopen (OUT, "w");

	fprintf (fout, "%d\n", nr);

	fclose (fout);
	return 0;
}

void read (char *filename)
{
	FILE *fin = fopen (IN, "r");
	int i;

	fscanf(fin, "%d%d", &N, &M);

	L.resize(N+1);
	for (i = 0; i < M; ++i)
	{
		int from, to;
		fscanf (fin, "%d%d", &from, &to);
		L[from].push_back(to);
		L[to].push_back(from);
	}

	fclose (fin);
}

void DFS ()
{
	C.resize (N+1);
	P.resize (N+1);
	S.resize (N+1);
	F.resize (N+1);

	int i;
	for (i = 1; i <= N; ++i)
		P[i] = NIL;

	for (i = 1 ; i <= N; ++i)
		if (C[i] == ALB)
		{
			nr++;
			DFSV (i);
		}
}

void DFSV (int s)
{
	REZ.push_back(s);
	C[s] = GRI;
	S[s] = ++t;

	list<int>::iterator i;
	for (i = L[s].begin(); i != L[s].end(); ++i)
		if (C[*i] == ALB)
		{
			P[*i] = s;
			DFSV (*i);
		}
	C[s] = NEGRU;
	F[s] = ++t;
}