Cod sursa(job #2259942)

Utilizator mihaicivMihai Vlad mihaiciv Data 13 octombrie 2018 23:28:58
Problema Parcurgere DFS - componente conexe Scor 25
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.31 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream f("dfs.in");
ofstream gout("dfs.out");

class Graph {
private:
    int n;
    int** a;
    int* Size;
    int* vis;
    void dfs(int x) {
        vis[x] = 1;
        for (int i = 0; i < Size[x]; ++i ) {
            int p = a[x][i];
            if (vis[p] == 0) {
                dfs(p);
            }
        }
    }
public:
    Graph(int V) {
        this->n = V;
        a = new int*[n + 1];
        Size = new int [n + 1];
        vis = new int [n + 1];
        for (int i = 1; i <= n; ++i) {
            a[i] = new int[n + 1];
            vis[i] = 0;
            Size[i] = 0;
        }
    }
    void addEdge(int n1, int n2) {
        a[n1][Size[n1]] = n2;
        Size[n1] ++;
    }
    int getConnexComponents() {
        int ConnexComponentsNumber = 0;
        for (int i = 1; i <= n; ++i) {
            if (vis[i] == 0) {
                ConnexComponentsNumber ++;
                dfs(i);
            }
        }
        return ConnexComponentsNumber;
    }
};

int main() {
    int n, m;
    f >> n >> m;
    Graph g(n);
    int x, y;
    for (int i = 1; i <= n; ++ i) {
        f >> x >> y;
        g.addEdge(x, y);
        g.addEdge(y, x);
    }
    gout << g.getConnexComponents();
    return 0;
}