Cod sursa(job #2322596)

Utilizator StefaniaHrincuStefania Hrincu StefaniaHrincu Data 17 ianuarie 2019 22:12:20
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.8 kb

#include <stdio.h>



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



typedef struct nod

{

	int x;

	nod *a;

} *pNod;

pNod v[100005];



void add(pNod &dest, int val)

{

	pNod p;

	p = new nod;

	p -> x = val;

	p -> a = dest;

	dest = p;

}



void citire()

{

	freopen("dfs.in","r",stdin);

	freopen("dfs.out","w",stdout);

	scanf("%d %d",&n,&m);

	int i, x, y;



	for (i = 1; i <= m; i++)

        {

		scanf("%d %d",&x,&y);

		add(v[x], y);

		add(v[y], x);

	}

}



void DFS(int nod)

{

	pNod p;

	viz[nod] = 1;

	for (p = v[nod]; p != NULL; p = p -> a) if (!viz[p -> x]) DFS(p -> x);

}



int main()

{

	citire();

	int i;

	for (i = 1; i <= n; i++) if (!viz[i]) { cnt++; DFS(i);}

	printf("%d\n",cnt);

	return 0;

}