Cod sursa(job #2192248)

Utilizator nicolaefilatNicolae Filat nicolaefilat Data 5 aprilie 2018 08:50:19
Problema Parcurgere DFS - componente conexe Scor 45
Compilator cpp Status done
Runda Arhiva educationala Marime 1.1 kb
#include <iostream>
#include <fstream>
#include <vector>
#define MAXN 100005

using namespace std;

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

class Graph{
private:
    int n;
    vector<int>v[MAXN];
    bool viz[MAXN];
    void dfs(int nod);
public:
    Graph(int n);
    void add_edge(int nod,int muchie);
    int dfs_untill(int n);
};

Graph::Graph(int n){
    this->n = n;
}
void Graph::add_edge(int nod,int muchie){
    v[nod].push_back(muchie);
}
void Graph::dfs(int nod){
    viz[nod] = true;
    int curent;
    for(int i = 0; i < v[nod].size(); i++){
        curent = v[nod][i];
        if(!viz[curent])
            dfs(curent);
    }
}
int Graph::dfs_untill(int n){
    int cnt = 0;
    for(int i = 1; i <= n; i++){
        if(!viz[i]){
            cnt++;
            dfs(i);
        }
    }
    return cnt;
}

int main()
{
    int n,m;
    in>>n>>m;
    Graph graf(n);
    for(int i = 1; i <= n; i++){
        int x,y;
        in>>x>>y;
        graf.add_edge(x,y);
        graf.add_edge(y,x);
    }
    out<<graf.dfs_untill(n);
    return 0;
}