Cod sursa(job #2741092)

Utilizator luca_raduluca 123 luca_radu Data 15 aprilie 2021 14:54:01
Problema Parcurgere DFS - componente conexe Scor 0
Compilator c-64 Status done
Runda Arhiva educationala Marime 0.76 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;
}