Cod sursa(job #219297)

Utilizator ada_sAda-Mihaela Solcan ada_s Data 6 noiembrie 2008 13:17:40
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.01 kb
#include <stdio.h>   
const long N=100000;   
long *a[N], x[N], y[N], d[N], viz[N];   
  
void bfs(long x);   
  
int main()   
{   
    long i, conex=0, n, m;   
    freopen("dfs.in", "r", stdin);   
    freopen("dfs.out", "w", stdout);   
    scanf("%ld%ld", &n, &m);   
	for (i=1; i<=m; i++)
	{
		scanf("%ld%ld", &x[i], &y[i]);
		d[x[i]]++;
		d[y[i]]++;
	}//for i
	for (i=1;i<=n; i++)
	{
		a[i]=new long[d[i]+1];
		a[i][0]=0;
	}//for i
	for (i=1; i<=m; i++)
	{
		a[x[i]][++a[x[i]][0]]=y[i];
		a[y[i]][++a[y[i]][0]]=x[i];
	}//for i
	for (i=1; i<=n; i++)   
        if (!viz[i])   
        {   
            conex++;   
            bfs(i);   
        }//if   
    printf("%ld", conex);      
	return 0;
}//main

void bfs(long x)
{
	long coada[100000], p=0, u=0, i, y;
	viz[x]=true;
	coada[++u]=x;
	p=u;
	while (p<=u)
	{
		x=coada[p++];
		for (i=1; i<=a[x][0]; i++)
		{
			y=a[x][i];
			if (!viz[y])
			{
				viz[y]=true;
				coada[++u]=y;
			}//if
		}//for i
	}//while
}//bfs