Cod sursa(job #595231)

Utilizator scipianusFMI Ciprian Olariu scipianus Data 11 iunie 2011 17:48:18
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.79 kb
#include<fstream>
#include<cstdlib>
using namespace std;
int n,m,start,sol;
int *A[100010];
bool vizitat[100010];

void DFS(int x)
{
	int i;
	vizitat[x]=true;
	for(i=1;i<=A[x][0];i++)
	{
		if(vizitat[A[x][i]]==false)
			DFS(A[x][i]);
	}
}

int main()
{
	int i,x,y;
	ifstream fin("dfs.in");
	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;
	}
	fin.close();
	
	for(i=1;i<=n;i++)
	{
		if(vizitat[i]==false)
		{
			sol++;
			DFS(i);
		}
	}
	
	ofstream fout("dfs.out");
	fout<<sol<<"\n";
	fout.close();
	return 0;
}