Cod sursa(job #535731)

Utilizator andra23Laura Draghici andra23 Data 17 februarie 2011 18:15:57
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.24 kb
#include<fstream>
#include<vector>
#define maxn 100005

using namespace std;

class graph {
    int n;
    vector <int> v[maxn];
    int comp;
    int viz[maxn];
    
    public:
    graph(int n) {
        this -> n = n;
        comp = 0;   
    }
    
    void add_edge(int x, int y) {
        v[x].push_back(y);
        v[y].push_back(x);    
    }
    
    int getcomp() {
        return comp;    
    }
    
    void components() {
        for (int i = 1; i <= n; i++)
            viz[i] = 0;  
        for (int i = 1; i <= n; i++) {
            if (viz[i] == 0) {
                comp++;
                dfs(i);
            }
        }
    }
    
    void dfs(int nod) {
        viz[nod] = 1;
        for (int i = 0; i < v[nod].size(); i++) {
            if (viz[v[nod][i]] == 0) {
                viz[v[nod][i]] = 1;
                dfs(v[nod][i]);
            }    
        }
    }
};

int main() {
    ifstream f("dfs.in");
    ofstream g("dfs.out");
    
    int n, m, s, x, y;
    f >> n >> m;
    
    graph gr = graph(n);
    for (int i = 1; i <= m; i++) {
        f >> x >> y;
        gr.add_edge(x, y);
    }
    
    gr.components();
    g << gr.getcomp() << '\n';
    
    return 0;  
}