Cod sursa(job #2326644)

Utilizator Kovacs_Alexandra_UVT_FMIKovacs Alexandra Kovacs_Alexandra_UVT_FMI Data 23 ianuarie 2019 19:55:27
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.84 kb
#include <fstream>
#include <stdlib.h>
using namespace std;

ifstream f("dfs.in");
ofstream g("dfs.out");

int *M[100001], n, vizitat[100001], m;

void citeste();
void DF(int i);

int main(){
	int rez=0;
	citeste();
	for(int i=1; i<=n; i++)
		if(!vizitat[i]){
			rez++;
			DF(i);
		}

	g<<rez<<"\n";
	g.close();
	return 0;
}

void citeste(){
	int x, y, i;
	f>>n>>m;

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

	for(i=1; i<=m; i++){
		f>>x>>y;
		M[x][0]++;
		M[x] = (int *)realloc(M[x], (M[x][0]+1)*sizeof(int));

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

		M[x][M[x][0]]=y;
		M[y][M[y][0]]=x;
	}
	f.close();
}

void DF(int i){
	vizitat[i]=1;
	for(int j=1; j<=M[i][0]; j++)
		if(!vizitat[M[i][j]])
			DF(M[i][j]);
}