Правка кода поиска мостов в графе

193
26 июня 2018, 21:50
#include "stdafx.h"
#include <iostream>
#include <conio.h>
#include <algorithm>
#include <time.h>
#include <stdlib.h>
using namespace std;

class Graf
{
private:
    int MaxNodes;//Максимальное кол-во узлов
    int *nodes;
    bool *used;
    int timer;
    int *tin, *fup;
    int count_tops;  // 
    int count_edge; // 
    int previous_edge; // 
    struct Node 
    {
        int firstTop; // ВЕРШИНА 1
        int secondTop; // ВЕРШИНА 2

    }*Nodes;
public:
    Graf(); // КОНСТРУКТОР
    void UnitGraf(); // 
    void dfs(int v, int p = -1);
    void find_bridges();
};
Graf::Graf()
{
    MaxNodes = 50;
    nodes = new int[MaxNodes];
    Nodes = new Node[MaxNodes];
    used = new bool[MaxNodes];
    tin = new int[MaxNodes];
    fup = new int[MaxNodes];
}
void Graf::UnitGraf()
{
    cout << "Enter count of tops" << endl;
    cin >> count_tops;
    cout << endl << "Enter count of edge" << endl;
    cin >> count_edge;

    cout << endl
        << "Count of edge :" << count_edge << endl
        << "Enter them like : top 1,top 2"
        << endl;
    for (int i = 0; i < count_edge; i++)
    {
        cout << endl << "Top 1 = "; cin >> Nodes[i].firstTop; //  
        cout << "Top 2 = "; cin >> Nodes[i].secondTop;
    }
    cout << endl << "Graph was enter" << endl;
}
void Graf::dfs(int v, int p)
{
    used[v] = true;
    tin[v] = fup[v] = timer++;
    for (int i = 0; i < MaxNodes; i++) {
        if (Nodes[i].firstTop != NULL && Nodes[i].secondTop != NULL) {
            int to = i;
            if (to == p) continue;
            if (used[to]) fup[v] = std::min(fup[v], tin[to]);
            else {
                dfs(to, v);
                fup[v] = min(fup[v], tin[to]);
                if (fup[to] > tin[v]) cout << "Bridge: " << v << " , " << to << endl;
            }
        }
    }
}
void Graf::find_bridges()
{
    timer = 0;
    for (int i = 0; i < MaxNodes; i++) {
        used[i] = false;
    }
    for (int i = 0; i < MaxNodes; i++) {
        if (!used[i]) dfs(i);
    }
}
int main() {
    Graf graf;
    graf.UnitGraf();
    graf.find_bridges();
}

Написал граф через классы на списку смежности. Помогите написать корректный алгоритм поиска мостов.

READ ALSO
Бесконечный скролл фона

Бесконечный скролл фона

Как можно сделать бесконечный скролл фона при этом не теряя гибкости процентных величин?

176
Два блока рядом, разные по высоте

Два блока рядом, разные по высоте

Есть ли в этом случае возможность выровнять <span class = "b"> по высоте как auto?

172
Как вывести данные по ключу объектов?

Как вывести данные по ключу объектов?

Есть массив объектовНужно сделать вывод данных по ключу со всех объектов, дело в том, что ключ который вводишь есть, значение у ключа тоже...

191
Помогите доделать игру на js

Помогите доделать игру на js

Игра называется крестики-ноликиВ ней осталось доделать "ничью"

209