Алгоритм поиска граней на плоском графе (C++) ⇐ C++

[Anonymous]

В колледже я работаю над заданием по алгоритму, которое включает в себя поиск вершин, принадлежащих грани строго плоского и связного графа. Однако я столкнулся с проблемой в одном из тестовых случаев и не знаю, как ее решить. Я нахожу на одну дополнительную грань больше, чем следовало бы при моем текущем методе посещения вершин/ребер. Может кто-нибудь подсказать?
Я правильно распознаю лица в двух тестовых случаях, к которым у меня есть доступ. Однако, например, в зависимости от того, где находится начальная точка и где она соединена, я нахожу одно лишнее лицо, что неверно. Как это исправить?
Моя логика посещения и поиска всех граней заключалась в том, чтобы преобразовать каждое ребро в два направленных, отслеживая, какие из них я посетил, а какие нет. Чтобы выбрать следующую вершину для посещения, я вычисляю угол (арктан) между двумя точками и посещаю следующую в порядке против часовой стрелки.
Я сортирую для каждой вершины ее соединяющие ее ребра своим соседям, циклически, используя arctan. Таким образом, я могу расположить края против часовой стрелки.
Вспомогательные функции:
relativeInclination: вычисляет относительный наклон между двумя точками.
sort_connections: сортирует соединения точки i на основе ее относительного наклона относительно опорной точки.
printFaces: печатает грани графика.
Функция DFS:
Функция dfs — это модифицированный поиск в глубину (DFS) для поиска граней графа.
В качестве параметров она принимает индекс текущей точки (i), индекс текущего соединения (j), общее количество вершин (n), граф (граф), посещенная матрица (посещенная) и позиции вершин (позиции).
DFS обходит граф, начиная с из каждой непосещенной вершины и отмечает посещенные вершины и соединения.
При обнаружении цикла или ребра завершается текущая грань и добавляется к вектору граней.
Основная функция :
Считывает количество вершин (n) и количество ребер (m).
Инициализирует структуры данных для представления графа, посещений и положений вершин.
/>Для каждой вершины он считывает ее координаты и связи с другими вершинами, обновляя граф и посещаемую матрицу.
Сортирует соединения каждой вершины на основе ее относительного наклона относительно этой вершины.
Начинается поиск в глубину (DFS) из каждой непосещенной вершины.
Печатает найденные грани.
Вывод:
Вывод состоит из печать количества граней, а затем для каждой грани печать количества вершин, из которых она состоит, и индексов этих вершин.
Пример:
некоторый график
На этом изображении у меня есть любой плоский и связный граф.
введите здесь описание изображения
На этом другом изображении у меня тот же график, но в том виде, в каком его видит мой код: одно ребро идет, а другое возвращается вместо исходного ребра. То есть я направляю край и дублирую его.
введите описание изображения здесь
На этом другом изображении у меня есть любая вершина, соединенная с четырьмя другими вершины. Первое ребро, если использовать порядок моего кода, будет (X, D), второе (X, A), третье (X, B) и четвертое (X, C). Но, как и часы, они работают циклически, поэтому, хотя (X, D) является первой относительно моей вершины X, перед ней (циклически) стоит (X, C). Важно помнить об этом при выборе ребер против часовой стрелки.
Формат ввода: Каждый тестовый пример состоит из нескольких строк. Первая строка содержит два целых числа, N и M, представляющие соответственно количество вершин и ребер входного графа G. Гарантируется, что G связен, 1 ≤ N, M ≤ 10^5 и V(G) = { 1, 2, . . . , Н}. i-я строка входных данных начинается с двух действительных чисел xi, yi, представляющих координаты вершины i в декартовой плоскости; гарантируется, что −10^4 ≤ xi, yi ≤ 10^4. В той же строке мы имеем положительное целое число di, обозначающее степень вершины i. По-прежнему в той же строке у нас есть di целых чисел от 1 до N, каждое из которых соответствует соседу i; гарантируется, что вершина не является соседом самой себя.
Формат вывода: первая строка вывода содержит целое число F, которое должно быть равно количеству граней G. Следующие F строк должны соответствовать F граням G; каждая строка начинается с целого числа Si, обозначающего размер i-й грани G; тогда есть целые числа Si, представляющие контур, соответствующий краю грани. Порядок граней не важен, но последовательные вершины на ребре грани должны быть смежными.

Код: Выделить всё

#include 

using namespace std;

#define _ ios_base::sync_with_stdio(0);cin.tie(0);
#define ff first
#define ss second
#define pb push_back

vector face;
vector faces;

double relativeInclination(double x1, double x2, double y1, double y2){
return atan2(y1 - y2, x1 - x2);
}

vector sort_connections(int i, vector& connections, vector
> pos){
double x_ref = pos[i].first;
double y_ref = pos[i].second;
sort(connections.begin(), connections.end(), [&](double a, double b) {
double incl_a = relativeInclination(pos[a].first, x_ref, pos[a].second, y_ref);
double incl_b = relativeInclination(pos[b].first, x_ref, pos[b].second, y_ref);
return incl_a < incl_b;
});

return connections;
}

void printFaces(){
cout  y;

pair v; v.ff = x, v.ss = y;
positions[i] = v;

int k; cin >> k;
while (k--){
int a; cin >> a; a--;
graph[i].pb(a); visited[i].pb(false);
}

}

for(int i = 0; i < n; i++){
graph[i] = sort_connections(i, graph[i], positions);
}

for(int i = 0; i < visited.size(); i++){
for(int j = 0; j < visited[i].size();  j++){
if(!visited[i][j]) {
face.pb(i);
dfs(i, i, j, graph[i][j], graph, visited, positions);
}
}
}

printFaces();

return 0;
}

Я размещаю тесты в формате кода, поскольку в текстовом формате форматирование неверно.

Код: Выделить всё

First Test

8 11
0 0 2 2 3
1 1 4 1 4 5 7
1 -1 5 1 4 5 6 7
2 0 2 2 3
4 0 3 2 3 6
4 -1.5 2 3 5
-3 0 3 2 3 8
-2 0 1 7

Expected Output

5
6 2 5 6 3 7 2
7 3 7 8 7 2 1 3
5 1 2 4 3 1
5 5 3 4 2 5
4 6 3 5 6

My output

5
7 1 3 7 8 7 2 1
5 1 2 4 3 1
6 2 7 3 6 5 2
5 2 5 3 4 2
4 3 5 6 3

In the first test, my output is correct, the order doesn't matter, just the vertex that are part of the face.

Second Test

12 23
-3 1 2 2 8
-1 2 5 1 3 5 7 8
0.5 3 3 2 5 4
2.5 1.65 3 3 5 6
0.5 1.65 5 2 3 4 6 7
2 0.15 4 4 5 7 10
0 0.5 6 2 5 6 8 9 10
-1.5 0.5 4 1 2 7 9
-0.75 -1.5 4 7 8 10 11
1.75 -1.4 5 6 7 9 11 12
0.25 -3 3 9 10 12
2.9 -2.85 2 10 11

Expected Output

13
11 1 8 9 11 12 10 6 4 3 2 1
4 1 2 8 1
4 3 2 5 3
4 2 8 7 2
4 2 5 7 2
4 3 4 5 3
4 5 7 6 5
4 5 4 6 5
4 7 8 9 7
4 7 9 10 7
4 7 6 10 7
4 9 10 11 9
4 10 11 12 10

My output

13
11 1 8 9 11 12 10 6 4 3 2 1
4 1 2 8 1
4 2 7 8 2
4 2 5 7 2
4 2 3 5 2
4 3 4 5 3
4 4 6 5 4
4 5 6 7 5
4 6 10 7 6
4 7 9 8 7
4 7 10 9 7
4 9 10 11 9
4 10 12 11 10

In the second one as well.

Third Test

11 15
0 0 3 2 3 9
1 1 4 1 4 5 7
1 -1 5 1 4 5 6 7
2 0 2 2 3
4 0 3 2 3 6
4 -1.5 2 3 5
-3 0 3 2 3 8
-2 0 1 7
0.5 0 3 1 10 11
0.75 0.5 2 11 9
0.75 -0.5 2 10 9

Expected output

6
10 1 3 4 2 1 9 10 11 9 1
7 1 2 7 8 7 3 1
6 2 5 6 3 7 2
5 2 4 3 5 2
4 3 6 5 3
4 9 11 10 9

My output

7
7 1 3 7 8 7 2 1
6 1 9 11 10 9 1
5 1 2 4 3 1
6 2 7 3 6 5 2
5 2 5 3 4 2
4 3 5 6 3
4 9 10 11 9

В третьем неверно. Он идентифицирует одно лишнее лицо.
Что мне делать?

Подробнее здесь: https://stackoverflow.com/questions/783 ... ar-graph-c