Cod sursa(job #3350261)

Utilizator marap2011Paun Mara marap2011 Data 6 aprilie 2026 18:56:58
Problema Parcurgere DFS - componente conexe Scor 45
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.84 kb
#include <bits/stdc++.h>
#define pi pair<int,int>
using namespace std;

ifstream fin ("dfs.in") ;
ofstream fout ("dfs.out") ;

vector < int > g[100005] ;
bool sel[100005] ;

void dfs ( int nod )
{
    sel[nod] = 1 ;
    for ( auto it : g[nod] )
        if ( sel[it] == 0 )
            dfs ( it ) ;
}

void solve ()
{
    int n , m , k ;
    fin >> n >> m >> k ;
    for ( int i = 1 ; i <= m ; i ++ )
    {
        int x , y ;
        fin >> x >> y ;
        g[x].push_back(y) ;
        g[y].push_back(x) ;
    }

    int cnt = 0 ;

    for ( int i = 1 ; i <= n ; i ++ )
        if ( ! sel[i] )
        {
            cnt ++ ;
            dfs ( i ) ;
        }

    fout << cnt ;
}

int main()
{
    std :: ios_base :: sync_with_stdio ( false ) ;
    fin.tie(0) ;
    fout.tie(0) ;
    solve() ;

    return 0;
}