Cod sursa(job #2220478)

Utilizator dragos.galeteanu2001Dragos Iulian dragos.galeteanu2001 Data 11 iulie 2018 20:48:24
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.87 kb
#include <cstdio>
#include <cstdlib>

using namespace std;

int n, m, nr, checked[100001];
int *a[100001];

void dfs(int x)
{
	checked[x] = 1;

	for (int i = 1; i <= a[x][0]; ++i)
		if (!checked[a[x][i]]) dfs(a[x][i]);
}

int main()
{
	FILE *in, *out;
	in = freopen("bfs.in", "r", stdin);
	out = freopen("bfs.out", "w", stdout);

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

	for (int i = 1; i <= n; ++i) {
		a[i] = (int *)realloc(a[i], sizeof(int));
		a[i][0] = 0;
	}

	while (m--) {
		int x, y;
		scanf("%d%d", &x, &y);

		++a[x][0];
		a[x] = (int *)realloc(a[x], (a[x][0] + 1) * sizeof(int));
		a[x][a[x][0]] = y;

		++a[y][0];
		a[y] = (int *)realloc(a[y], (a[y][0] + 1) * sizeof(int));
		a[y][a[y][0]] = x;
	}

	for (int i = 1; i <= n; ++i)
		if (!checked[i]) {
			++nr;
			dfs(i);
		}

	printf("%d", nr);

	fclose(in);
	fclose(out);

    return 0;
}