Cod sursa(job #1315736)

Utilizator tudoras8tudoras8 tudoras8 Data 13 ianuarie 2015 01:05:01
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.42 kb
#include <cstring>

#define NMAX 100001

struct node {
    int key;
    node *next;
    node() {
        next = NULL;
    }
};

class List {
    private:
        node *first, *last;
    public:
        List() {
            first = last = NULL;
        }
        node *front() {
            return first;
        }
        void push_back(int key) {
            node *p;
            p = new node;
            p->key = key;

            if (last != NULL) last->next = p;
            else first = p;
            last = p;
        }
};

class stack {
    private:
        node *first;
    public:
        stack() {
            first = NULL;
        }
        int top() {
            if (first != NULL) return first->key;
        }
        bool empty() {
            if (first == NULL) return 1;
            return 0;
        }
        void pop() {
            node *p = first;
            first = first->next;
            delete p;
        }
        void push(int x) {
            node *p;
            p = new node;
            p->key = x;
            p->next = first;
            first = p;
        }
};

class Graph {
    private:
        int N, components, comp[NMAX];
        List v[NMAX];
        bool visited[NMAX];

        void visit(int node) {
            comp[node] = components;
        }

    public:
        Graph() {
            memset(v, NULL, sizeof(v));
            memset(comp, 0, sizeof(comp));
            memset(comp, 0, sizeof(visited));
        }
        void setSize(int n) {
            N = n;
        }
        void addEdge(int i, int j) {
            v[i].push_back(j);
        }
        void DFS(int Node) {
            node *p;
            p = v[Node].front();
            visit(Node);
            visited[Node] = 1;

            while (p != NULL) {
                if (!visited[p->key])
                    DFS(p->key);
                p = p->next;
            }
        }
        int getComponents() {
            components = 0;
            for (int i = 1; i <= N; i++) {
                if (!visited[i]) {
                    components++;
                    DFS(i);
                }
            }

            return components;
        }
} G;

#include <fstream>

using namespace std;

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

int main()
{
    int N, M;
    f >> N >> M;
    G.setSize(N);

    int x, y;
    while (M--) {
        f >> x >> y;
        G.addEdge(x, y);
        G.addEdge(y, x);
    }
    g << G.getComponents();
    return 0;
}