Cod sursa(job #504465)

Utilizator newsabbathCaraman Sabina newsabbath Data 27 noiembrie 2010 19:13:20
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.82 kb
#include <stdio.h>

int n, m, viz[100005], cnt;

struct graf
{
	int x;
	graf *next;
} *L[100005];

void add(graf *& prim, int val)
{
	graf *p = new graf;
	p -> x = val;
	p -> next = prim;;
	prim= p;
}

void citire()
{
	freopen("dfs.in","r",stdin);
	freopen("dfs.out","w",stdout);
	scanf("%d %d",&n,&m);

	for (int i = 0; i < m; i++)
	{
	    int x,y;
		scanf("%d %d",&x,&y);
		add(L[x], y);
		add(L[y], x);
	}
}

void DFS(int nod)
{
	viz[nod] = 1;
	for (graf *p = L[nod]; p != NULL; p = p -> next)
        if (!viz[p -> x])
            DFS(p -> x);
}

int numar()
{
    int nc = 0;
    for(int i=1;i<=n;i++)
        if(viz[i] == 0)
            {
                nc++;
                DFS(i);
            }
    return nc;
}
int main()
{
	citire();
	printf("%d\n",numar());
	return 0;
}