Cod sursa(job #3325611)

Utilizator CosminaneBoac Mihai Cosmin Cosminane Data 25 noiembrie 2025 20:11:24
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.58 kb
#include <fstream>
#include <vector>
using namespace std;
vector <int> v[100005];
int f[100005];
void dfs( int x ){
	int i, y;
	for( i = 0; i < v[x].size(); i++ ){
		y = v[x][i];
		if( f[y] == 0 ){
			f[y] = 1;
			dfs( y );
		}
	}
}
int main(){
	int n, m, i, x, y, ras;
	ifstream fin( "dfs.in" );
	ofstream fout( "dfs.out" );
	fin >> n >> m;
	for( i = 0; i < m; i++ ){
		fin >> x >> y;
		v[x].push_back( y );
		v[y].push_back( x );
	}
	ras = 0;
	for( i = 1; i <= n; i++ ){
		if( f[i] == 0 ){
			f[i] = 1;
			dfs( i );
			ras++;
		}
	}
	fout << ras;
	return 0;
}