problema marciano

// Narciso Nunes de Queiroz Neto

#include <iostream>


using namespace std;

template <typename T>
class Vector {
private:
    T* data;
    size_t capacity;
    size_t size;

public:
    Vector() : data(nullptr), capacity(0), size(0) {}

    ~Vector() {
        delete[] data;
    }

    void resize(size_t new_capacity) {
        T* new_data = new T[new_capacity];
        for (size_t i = 0; i < size; ++i) {
            new_data[i] = data[i];
        }
        delete[] data;
        data = new_data;
        capacity = new_capacity;
    }

    void push_back(const T& value) {
        if (size == capacity) {
            resize(capacity == 0 ? 1 : 2 * capacity);
        }
        data[size++] = value;
    }

    T& operator[](size_t index) {
        return data[index];
    }

    const T& operator[](size_t index) const {
        return data[index];
    }

    size_t getSize() const {
        return size;
    }

    void reverse() {
        for (size_t i = 0; i < size / 2; ++i) {
            T temp = data[i];
            data[i] = data[size - i - 1];
            data[size - i - 1] = temp;
        }
    }

    void sortDescending() {
        for (size_t i = 0; i < size - 1; ++i) {
            for (size_t j = i + 1; j < size; ++j) {
                if (data[i] < data[j]) {
                    T temp = data[i];
                    data[i] = data[j];
                    data[j] = temp;
                }
            }
        }
    }
};

// Classe Queue (Fila)
template <typename T>
class Queue {
private:
    struct Node {
        T data;
        Node* next;
        Node(const T& data) : data(data), next(nullptr) {}
    };

    Node* front;
    Node* back;
    size_t size;

public:
    Queue() : front(nullptr), back(nullptr), size(0) {}

    ~Queue() {
        while (!isEmpty()) {
            desenfileirar();
        }
    }

    void enfileirar(const T& value) {
        Node* newNode = new Node(value);
        if (isEmpty()) {
            front = back = newNode;
        } else {
            back->next = newNode;
            back = newNode;
        }
        ++size;
    }

    void desenfileirar() {
        if (!isEmpty()) {
            Node* temp = front;
            front = front->next;
            delete temp;
            --size;
        }
    }

    T& getFront() {
        return front->data;
    }

    const T& getFront() const {
        return front->data;
    }

    bool isEmpty() const {
        return size == 0;
    }

    size_t getSize() const {
        return size;
    }
};

// Classe Stack (Pilha)
template <typename T>
class Stack {
private:
    struct Node {
        T data;
        Node* next;
        Node(const T& data) : data(data), next(nullptr) {}
    };

    Node* top;
    size_t size;

public:
    Stack() : top(nullptr), size(0) {}

    ~Stack() {
        while (!isEmpty()) {
            pop();
        }
    }

    void push(const T& value) {
        Node* newNode = new Node(value);
        newNode->next = top;
        top = newNode;
        ++size;
    }

    void pop() {
        if (!isEmpty()) {
            Node* temp = top;
            top = top->next;
            delete temp;
            --size;
        }
    }

    T& topElement() {
        return top->data;
    }

    const T& topElement() const {
        return top->data;
    }

    bool isEmpty() const {
        return size == 0;
    }

    size_t getSize() const {
        return size;
    }
};

// Estrutura para representar um grafo usando lista de adjacência
class Graph {
    int V;
    Vector<Vector<int>> adj;

public:
    Graph(int V) : V(V) {
        adj.resize(V);
    }

    void addEdge(int v, int w) {
        adj[v].push_back(w);
    }

    void BFS(int start, int end) {
        Vector<bool> visited;
        visited.resize(V);

        Vector<int> predecessor;
        predecessor.resize(V);

        for(int i = 0; i < V; i++){
            visited[i] = false;
            predecessor[i] = -1;
        }

        Queue<int> fila;
        visited[start] = true;
        fila.enfileirar(start);

        while (!fila.isEmpty()) {
            int current = fila.getFront();
            fila.desenfileirar();

            if (current == end) {
                break;  // Parar se o destino for encontrado
            }

            for (size_t i = 0; i < adj[current].getSize(); ++i) {
                int adjacent = adj[current][i];
                if (!visited[adjacent]) {
                    visited[adjacent] = true;
                    predecessor[adjacent] = current;  // Atualiza o predecessor
                    fila.enfileirar(adjacent);
                }
            }
        }

        // Reconstruir o caminho do destino ao início
        Vector<int> path;
        if (visited[end]) {
            for (int v = end; v != -1; v = predecessor[v]) {
                path.push_back(v);
            }
            path.reverse(); // Inverter o caminho para começar do início

            cout << "Caminho mais curto entre " << start << " e " << end << ": ";
            for (size_t i = 0; i < path.getSize(); ++i) {
                cout << path[i];
                if (i < path.getSize() - 1) {
                    cout << ",";
                }
            }
            cout << endl;
        } else {
            cout << "Não há caminho entre " << start << " e " << end << endl;
        }
    }

    Vector<int> DFS(int start) {
        Vector<bool> visited;
        visited.resize(V);

        for(int i = 0; i < V; i++){
            visited[i] = false;
        }

        Vector<int> order;
        Stack<int> pilha;

        pilha.push(start);

        while (!pilha.isEmpty()) {
            int current = pilha.topElement();
            pilha.pop();

            if (!visited[current]) {
                visited[current] = true;
                order.push_back(current);

                for (size_t i = 0; i < adj[current].getSize(); ++i) {
                    int adjacent = adj[current][i];
                    if (!visited[adjacent]) {
                        pilha.push(adjacent);
                    }
                }
            }
        }

        // Ordem do DFS já é a ordem de visita
        // cout << "Ordem de visitação (DFS): ";
        // for (size_t i = 0; i < order.getSize(); ++i) {
        //     cout << order[i] << " ";
        // }
        // cout << endl;

        // Identificar vértices desconexos
        Vector<int> disconnected;
        for (int i = 0; i < V; ++i) {
            if (!visited[i]) {
                disconnected.push_back(i);
            }
        }

        disconnected.sortDescending();

        // cout << "Vértices desconexos após DFS: ";
        // if (disconnected.getSize() == 0) {
        //     cout << "Nenhum";
        // } else {
        //     for (size_t i = 0; i < disconnected.getSize(); ++i) {
        //         cout << disconnected[i] << " ";
        //     }
        // }
        // cout << endl;

        for (size_t i = 0; i < disconnected.getSize(); ++i) {
                cout << disconnected[i] << " ";
            }

        for (size_t i = 0; i < order.getSize(); ++i) {
            cout << order[i] << " ";
        }

        return disconnected;
    }
};

int main() {
    int quant, arestas;
    cin >> quant;
    cin >> arestas;
    Graph g(quant);
    int escolha;

    cout<< "1 para DFS e 2 para BFS\n";
    cin>>escolha;

    if(escolha == 1){
        for (int i = 0; i < arestas; i++) {
            int vertice, adjacencia;
            cin >> vertice >> adjacencia;
            g.addEdge(vertice, adjacencia);
        }

        cout << "Busca em Profundidade (DFS) começando a partir do vértice 0:\n";
        g.DFS(0);
    }

    if(escolha == 2){
        int começo, fim;
        for (int i = 0; i < arestas+1; i++) {
            int vertice, adjacencia;
            cin >> vertice >> adjacencia;
            g.addEdge(vertice, adjacencia);

            começo = vertice;
            fim = adjacencia;
        }

        cout << "A"<< começo<<" B: "<<fim;
        g.BFS(começo, fim);  // Aqui você pode ajustar o destino
    }


    return 0;
}