Cod sursa(job #247477)

Utilizator ZillaMathe Bogdan Zilla Data 23 ianuarie 2009 08:12:24
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.03 kb
#include <stdio.h>

struct elem
{
	int nod;
	elem *next;
};

elem *p[100001];

int vizitat_df[100001];

void adauga(int j,int k)
{
	elem *newel=new elem;
	newel->nod=k;
	if (p[j]==NULL)
		{
			p[j]=newel;
			newel->next=NULL;
		}
	else
		{
			newel->next=p[j];
			p[j]=newel;
		}
}

void DF(int x)
{
	elem *current=p[x];

	while(current!=NULL)
		{
			if(vizitat_df[current->nod]==0)
				{
                	vizitat_df[current->nod]=1;
					DF(current->nod);
				}
			current=current->next;
		}
}


int main()
{
    int n,m,i,x,y,nr=0;
    freopen("dfs.in","r",stdin);
    freopen("dfs.out","w",stdout);    
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;++i)
        {
            scanf("%d%d",&x,&y);
            adauga(x,y);
            adauga(y,x);
        }
    for(i=1;i<=n;++i)
        {
            if(vizitat_df[i]==0)
                {
                    ++nr;
                    DF(i);
                    vizitat_df[i]=1;
                }
        }
    printf("%d",nr);
	return 0;
}