Cod sursa(job #3145823)

Utilizator radu1331Mocan Radu radu1331 Data 17 august 2023 10:52:03
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.79 kb
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
const int NMAX = 1e5 + 2;
vector<int> adj[NMAX];
bool viz[NMAX];

void dfs ( int nod )
{
	viz [ nod ] = 1;
	for ( auto& to : adj [ nod ] )
	{
		if ( ! viz [ to ] )
			dfs ( to );
	}
}

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