Cod sursa(job #2192249)

Utilizator nicolaefilatNicolae Filat nicolaefilat Data 5 aprilie 2018 09:00:35
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.37 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);
    void afis(int n);
    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::afis(int n){
    for(int i = 1; i <= n; i++){
        cerr<<i<<" : ";
        for(int j = 0; j < v[i].size(); j++)
            cerr<<v[i][j]<<" ";
        cerr<<endl;
    }
}
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){

    for(int i = 1; i <= n; i++)
        viz[i] = false;
    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 <= m; i++){
        int x,y;
        in>>x>>y;
        graf.add_edge(x,y);
        graf.add_edge(y,x);
    }
    out<<graf.dfs_untill(n);
    return 0;
}