Cod sursa(job #2854240)

Utilizator teodorescunicolasteodorescu nicolas alexandru teodorescunicolas Data 21 februarie 2022 08:48:11
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.92 kb
#include <stdio.h>
#include <vector>

#define NMAXX 100000

using namespace std;

struct nodes {
    int subset;
    vector <int> edges;
};


nodes graf[NMAXX];

void dfs( int i, int s ) {
    graf[i].subset = s;

    for ( int neighbour : graf[i].edges ) {
        if ( graf[neighbour].subset != s )
            dfs( neighbour, s );
    }
}

int main()
{
    FILE *fin, *fout;
    int n, m, i, nrSubset, a, b;

    fin = fopen( "dfs.in", "r" );
    fout = fopen( "dfs.out", "w" );

    fscanf( fin, "%d%d", &n, &m );
    for ( i = 0; i < m; i++ ) {
        fscanf( fin, "%d%d", &a, &b );
        graf[a].edges.push_back( b );
        graf[b].edges.push_back( a );
    }

    nrSubset = 0;
    for ( i = 1; i <= n; i++ ) {
        if ( graf[i].subset == 0 )
            dfs( i, ++nrSubset );
    }

    fprintf( fout, "%d", nrSubset );

    fclose( fin );
    fclose( fout );
    return 0;
}