Cod sursa(job #2740275)

Utilizator Radu_FilipescuFilipescu Radu Radu_Filipescu Data 12 aprilie 2021 13:10:35
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.76 kb
#include <fstream>
#include <vector>

using namespace std;

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

int n, m;
vector <int> ad[100002];
int vis[100002], nr_comp;

void dfs( int nod ) {
    vis[nod] = 1;

    int w;
    for( int i = 0; i < ad[nod].size(); i++ ) {
        w = ad[nod][i];

        if( vis[w] == 0 )
            dfs( w );
    }
}

int main()
{
    fin >> n >> m;

    int x, y;
    for( int i = 1; i <= m; i++ ) {
        fin >> x >> y;

        /// adaugam o muchie in graf

        ad[x].push_back( y );
        ad[y].push_back( x );
    }

    for( int i = 1; i <= n; ++i )
        if( vis[i] == 0 ) {
            nr_comp++;

            dfs( i );
        }

    fout << nr_comp;

    return 0;
}