Cod sursa(job #577969)

Utilizator darkseekerBoaca Cosmin darkseeker Data 10 aprilie 2011 20:32:27
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.87 kb
#include <fstream>
#include <cstdio>
#include <cstdlib>
#define NMAX 100007
#define Input "dfs.in"
#define Output "dfs.out"
using namespace std;

bool viz[NMAX];
int N,M;
int* a[NMAX];

ofstream fout(Output);

inline void push(int e1,int e2)
{
	a[e1]=(int*)realloc(a[e1],(++a[e1][0]+1)*sizeof(int));
	a[e2]=(int*)realloc(a[e2],(++a[e2][0]+1)*sizeof(int));
	a[e1][a[e1][0]]=e2;
	a[e2][a[e2][0]]=e1;
}

inline void read()
{
	ifstream fin(Input);
	fin>>N>>M;
	int i,e1,e2;
	for(i=1; i<=N; i++)
		a[i]=(int*)realloc(a[i],sizeof(int)) ,a[i][0]=0;
	for(i=1; i<=M; i++)
		 fin>>e1>>e2,push(e1,e2);
}

inline void df(int nod)
{
	viz[nod]=1;
	int i;
	for(i=1; i<=a[nod][0]; i++)
		if(!viz[a[nod][i]])
			df(a[nod][i]);
}

int main(){
	
	int i,nrc=0;
	read();
	for(i=1; i<=N; i++)
		if(!viz[i])
			nrc++,df(i);
	fout<<nrc<<'\n';
	
	return 0;
}