Grafos/CadeiaAlimentar.cpp at master · mbrunoviegas/Grafos · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
#include <iostream>
#include <cstring>
#include <climits>

using namespace std;

class Graph
{

private:
    int numVertices;
    int **matrix;

public:
    Graph(int numVertices)
    {
        this->numVertices = numVertices;
        this->matrix = new int *[numVertices];

        for (int i = 0; i < this->numVertices; i++)
            matrix[i] = new int[numVertices];

        for (int i = 0; i < this->numVertices; i++)
            memset(matrix[i], 0, this->numVertices * sizeof(int));
    }

    ~Graph()
    {
        for (int i = 0; i < numVertices; i++)
            delete[] this->matrix[i];
        delete[] this->matrix;
    }

    void buildMatrix(int v1, int v2)
    {
        matrix[v1 - 1][v2 - 1] = 1;
    }

    int minDistance(int dist[], bool sptSet[])
    {
        int min = INT_MAX, min_index;

        for (int v = 0; v < this->numVertices; v++)
        {
            if (sptSet[v] == false && dist[v] <= min)
            {
                min = dist[v], min_index = v;
            }
        }
        return min_index;
    }

    void dijkstra(int u, int *dist)
    {
        bool sptSet[this->numVertices];

        for (int i = 0; i < this->numVertices; i++)
            dist[i] = INT_MAX, sptSet[i] = false;

        dist[u] = 0;

        for (int count = 0; count < this->numVertices - 1; count++)
        {
            u = minDistance(dist, sptSet);
            sptSet[u] = true;
            for (int v = 0; v < this->numVertices; v++)
                if (!sptSet[v] && matrix[u][v] && dist[u] != INT_MAX && dist[u] + matrix[u][v] < dist[v])
                    dist[v] = dist[u] + matrix[u][v];
        }
    }
};

int main()
{
    int numVertices;
    int numEdges;
    int v1;
    int v2;

    cin >> numVertices >> numEdges;

    Graph *graph = new Graph(numVertices);

    for (int i = 0; i < numEdges; i++)
    {
        cin >> v1 >> v2;
        graph->buildMatrix(v1, v2);
    }

    int *dist = new int[numVertices];
    memset(dist, 0, numVertices * sizeof(int));

    int *dist2 = new int[numVertices];
    memset(dist2, 0, numVertices * sizeof(int));

    graph->dijkstra(0, dist);

    for (int i = 0; i < numVertices; i++)
    {
        if (dist[i] == INT_MAX)
        {
            graph->dijkstra(i, dist2);

            if (dist2[0] == INT_MAX)
            {
                cout << "Nao Bolada" << endl;
                break;
            }
            else
            {
                cout << "Bolada" << endl;
                break;
            }
        }
        else if (i == numVertices - 1)
        {
            cout << "Bolada" << endl;
            break;
        }
    }
    delete dist;
    delete dist2;
    delete graph;

    return 0;
}