Cod sursa(job #3161867)

Utilizator radu1331Mocan Radu radu1331 Data 28 octombrie 2023 09:46:54
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.86 kb
#include <iostream>
#include <vector>
#pragma GCC optimize("O3")

const int NMAX = 1e5 + 5;

std::vector<int> v [ NMAX ];
bool viz [ NMAX ];

void dfs ( int k );

int main ()
{
	( void )! freopen ( "dfs.in" , "r" , stdin );
	( void )! freopen ( "dfs.out" , "w" , stdout );
    std::ios_base::sync_with_stdio ( false );
    std::cin.tie ( NULL );
    int n, m; std::cin >> n >> m;
    int x, y;
    for ( int i = 0; i < m; ++ i )
    {
    	std::cin >> x >> y;
    	v [ x ].push_back( y ), v [ y ].push_back( x );
    }
    int total = 0;
    for ( int i = 1; i <= n; ++ i )
    {
    	if ( ! viz [ i ] )
    		dfs ( i ), ++ total;
    }
    std::cout << total;
    return 0;
}

void dfs ( int k )
{
	viz [ k ] = 1;
  	for ( int i = 0; i < ( int ) v [ k ].size(); ++ i )
    	if ( ! viz [ v [ k ] [ i ] ] )
      		dfs ( v [ k ] [ i ] );
}