Cod sursa(job #3219188)

Utilizator andrei_botorogeanuBotorogeanu Andrei andrei_botorogeanu Data 30 martie 2024 13:04:13
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.93 kb
#include<iostream>
#include<vector>
#define SIZE 10000000
#define FIN "dfs.in"
#define FOUT "dfs.out"
#define pb push_back

using namespace std;

int N, //numarul de noduri
	M; //numarul de muchii

vector<int> Graph[SIZE]; 

int visited[SIZE],
	components;

void readGraph() {

	int x, y;
	
	freopen(FIN, "r", stdin);
	
	cin>>N>>M;
	
	for(int i=1; i<=M; ++i) {
		
		cin>>x>>y;
		
		Graph[x].pb(y);
		Graph[y].pb(x);
	}		
} 

void DFS(int node) {
	
	visited[ node ] = 1;
	
	for(int i=0; i<Graph[node].size(); i++) {
	
		int descendent =Graph[node][i];
	
		if(!visited[descendent]) 
			DFS(descendent);
	}
}

void find_components_connex() {
	for(int node = 1; node<=N; node++) {
		if( !visited[ node ] ) {
			
			components++;
			
			DFS(node);
		}
	}
	freopen(FOUT, "w", stdout);
	cout<<components;
}

int main(int argc, char const *argv[])
{
	readGraph();
	find_components_connex();
}