Cod sursa(job #185269)

Utilizator Astrid28Ruxandra Cohal Astrid28 Data 24 aprilie 2008 23:16:51
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.81 kb
#include<fstream.h>
#include<stdlib.h>

int n,m,nr;
int *a[100000],viz[100000];



void citire()
{
	ifstream fin("dfs.in");
	int i,x,y;
	fin>>n>>m;
	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>>x>>y;
			a[x][0]++;
			a[x]=(int *) realloc(a[x],(a[x][0]+1)*sizeof(int));
			a[x][a[x][0]]=y;
			a[y][0]++;
			a[y]=(int *) realloc(a[y],(a[y][0]+1)*sizeof(int));
			a[y][a[y][0]]=x;
		}
}


void DFS(int x)
{
	int i;
	viz[x]=nr;
	for(i=1;i<=a[x][0];i++)
		if(!viz[a[x][i]])
			{
				viz[a[x][i]]=1;
				DFS(a[x][i]);
			}
}



int main()
{
	int i;
	ofstream fout("dfs.out");
	citire();
	for(i=1;i<=n;i++)
		if(!viz[i])
			{
				nr++;
				DFS(i);
			}
	fout<<nr;
	fout<<'\n';
	fout.close();
	return 0;
}