Cod sursa(job #2780162)

Utilizator Teo_1101Mititelu Teodor Teo_1101 Data 6 octombrie 2021 10:52:51
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.03 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

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

const int NMAX = 100001;

class graf{
    vector < int > Ad[NMAX];
    int N;
public:
    graf(int n):N(n){}
    void addEdge(int x, int y){
        Ad[x].push_back( y );
        Ad[y].push_back( x );
    }
    void DFS( int nod, bool vis[] ){
        vis[nod] = 1;
        for( int i = 0; i < Ad[nod].size(); ++i ){
            int w = Ad[nod][i];
            if( vis[w] == 0 )DFS(w,vis);
        }
    }
    int nrComponenteConexe(){
        int nr = 0;
        bool vis[NMAX] = {0};
        for( int i = 1; i <= N; ++i )
            if( vis[i] == 0 ){
                DFS(i,vis);
                nr++;
            }
        return nr;
    }

};

int main()
{
    int N, M, x, y;
    fin  >> N >> M;

    graf G(N);
    for( int i = 1; i <= M; ++i ){
        fin >> x >> y;
        G.addEdge(x,y);
    }
    fout << G.nrComponenteConexe() << '\n';
    return 0;
}