Cod sursa(job #2475772)

Utilizator copanelTudor Roman copanel Data 17 octombrie 2019 16:09:59
Problema Parcurgere DFS - componente conexe Scor 0
Compilator c-64 Status done
Runda Arhiva educationala Marime 0.74 kb
#include <stdio.h>
#include <stdbool.h>

int vf[400001], urm[400001], lst[100001];
int nr = -1;
bool viz[100001];

void adauga(int x, int y) {
	vf[++nr] = y;
	urm[nr] = lst[x];
	lst[x] = nr;
}

void dfs(int x) {
	viz[x] = true;
	int y;
	for (int p = lst[x]; p != 0; p = urm[p]) {
		y = vf[p];
		if (viz[y] == false) {
			dfs(y);
		}
	}
}

int main() {
	FILE *fin, *fout;
	int n, m, comp;

	fin = fopen("dfs.in", "r");
	fscanf(fin, "%d%d", &n, &m);
	for (int i = 0; i < m; i++) {
		int a, b;
		fscanf(fin, "%d%d", &a, &b);
		adauga(a, b);
		adauga(b, a);
	}
	fclose(fin);

	comp = 0;
	for (int i = 1; i <= nr; i++) {
		if (viz[i] == false) {
			dfs(i);
			comp++;
		}
	}

	fout = fopen("dfs.out", "w");
	fprintf(fout, "%d", comp);
	fclose(fout);
	return 0;
}