Cod sursa(job #2274605)

Utilizator cezar.plescaCezar Plesca cezar.plesca Data 2 noiembrie 2018 10:15:11
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.79 kb
#include<stdio.h>
#include<stdlib.h>
#include<vector>
#include <queue>

using namespace std;

int M,N;

vector<int> L[100000];
bool visited[100000]; // vector pentru marcarea nodurilor

void depth(int nod){
	// procesarea nodului de indice nod
	visited[nod]=true;
	vector<int>::iterator it; 
	for (it = L[nod].begin(); it != L[nod].end(); ++it) {
		if(visited[*it]==false)
			depth(*it);	
	}
}

int main(){
	FILE* f= fopen("dfs.in","rt");
	FILE* g= fopen("dfs.out","wt");
	fscanf(f,"%d %d",&N,&M);

	int x,y;
	int nb=0;

	for(int i=0;i<M;i++){
		fscanf(f,"%d %d",&x,&y);
		L[x-1].push_back(y-1);	
		L[y-1].push_back(x-1);
	}

	for(int i=0;i<N;i++){
		if(visited[i]==false){
			depth(i);
			nb++;
		}
	}

	fprintf(g,"%d",nb);

	fclose(g);
	fclose(f);
	return 0;
}