Cod sursa(job #574104)

Utilizator horeste12Stoianovici Horatiu Andrei horeste12 Data 6 aprilie 2011 20:24:07
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.87 kb
#include<cstdio>
using namespace std;

FILE *f;
FILE *g;

typedef struct nod
{
	int inf;
	nod *urm;
} NOD;

typedef NOD *graf[100010];
graf G;

int n,m,nr;
int c[100010],viz[100010];
void citire()
{
	f=fopen("dfs.in","r");
	fscanf(f,"%d %d",&n,&m);
	NOD *p;
	int a,b;
	for(int i=1;i<=m;i++)
	{
		fscanf(f,"%d %d",&a,&b);
		p=new NOD;
		p->inf=b; p->urm=G[a]; G[a]=p;
		p=new NOD;
		p->inf=a; p->urm=G[b]; G[b]=p;
	}
}

void bfs(int s)
{
	int pr,ul=pr=1;
	c[pr]=s;
	viz[s]=1;
	while(pr<=ul)
	{
		NOD *p;
		p=G[c[pr]];
		while(p)
		{
			if(!viz[p->inf])
			{
				c[++ul]=p->inf;viz[p->inf]=1;
			}
			p=p->urm;
		}
		pr++;
	}
}

void afis()
{
	g=fopen("dfs.out","w");
	fprintf(g,"%d\n",nr);
	fclose(f);
	fclose(g);
}

int main()
{
	citire();
	for(int i=1;i<=n;i++)
		if(!viz[i])
		{	bfs(i);nr++;};
	afis();
	return 0;
}