Cod sursa(job #2779802)

Utilizator vmnechitaNechita Vlad-Mihai vmnechita Data 4 octombrie 2021 23:38:15
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.72 kb
#include <bits/stdc++.h>
#define NMAX 100005
#define pb push_back

using namespace std;

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

vector < int > v[NMAX];
bool fr[NMAX];

void dfs ( int nod );

int main()
{
    int n, m, x, y, nr, i;

    fin >> n >> m;
    while ( m-- )
    {
        fin >> x >> y;
        v[x].pb ( y ), v[y].pb ( x );
    }

    nr = 0;
    for ( i = 1; i <= n; i++ )
        if ( fr[i] == 0 )
        {
            nr++;
            dfs ( i );
        }

    fout << nr;

    return 0;
}

void dfs ( int nod )
{
    vector < int > :: iterator it;

    fr[nod] = 1;
    for ( it = v[nod].begin(); it != v[nod].end(); it++ ) if ( fr[*it] == 0 ) dfs ( *it );
}