Поиск граней на плоском графе (c++)

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

1 сообщение • Страница 1 из 1

Anonymous

Цитата

Сообщение Anonymous » 18 апр 2024, 00:09

В колледже я работаю над заданием по алгоритму, которое включает в себя поиск вершин, принадлежащих грани строго плоского и связного графа. Однако я столкнулся с проблемой в одном из тестовых случаев и не знаю, как ее решить. Я нахожу на одну дополнительную грань больше, чем следовало бы при моем текущем методе посещения вершин/ребер. Может ли кто-нибудь подсказать мне?
Я правильно идентифицирую лица в двух тестовых случаях, к которым у меня есть доступ. Однако, например, в зависимости от того, где находится начальная точка и где она соединена, я нахожу одно лишнее лицо, что неверно. Как это исправить?
Моя логика посещения и поиска всех граней заключалась в том, чтобы преобразовать каждое ребро в два направленных, отслеживая, какие из них я посетил, а какие нет. Чтобы выбрать следующий для посещения, я вычисляю угол (арктан) между двумя точками и посещаю следующую в порядке против часовой стрелки.
Ниже приведены скриншоты пройденных мной случаев и случаев Я терплю неудачу.
Формат ввода: Каждый тестовый пример состоит из нескольких строк. Первая строка содержит два целых числа, 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 rep(i,x,n) for(int i=x;i=x;i--)
#define forr(v) for(auto& x: v)
#define all(a) (a).begin(), (a).end()
#define endl '\n'
#define ff first
#define ss second
#define pb push_back

typedef long long ll;
typedef pair ii;
typedef vector vi;
typedef vector vl;

const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3fll;

void DBG() {
cerr 

Подробнее здесь: [url]https://stackoverflow.com/questions/78343772/finding-faces-on-a-planar-graph-c[/url]

1713388186

Anonymous

В колледже я работаю над заданием по алгоритму, которое включает в себя поиск вершин, принадлежащих грани строго плоского и связного графа. Однако я столкнулся с проблемой в одном из тестовых случаев и не знаю, как ее решить. Я нахожу на одну дополнительную грань больше, чем следовало бы при моем текущем методе посещения вершин/ребер. Может ли кто-нибудь подсказать мне?
Я правильно идентифицирую лица в двух тестовых случаях, к которым у меня есть доступ. Однако, например, в зависимости от того, где находится начальная точка и где она соединена, я нахожу одно лишнее лицо, что неверно. Как это исправить?
Моя логика посещения и поиска всех граней заключалась в том, чтобы преобразовать каждое ребро в два направленных, отслеживая, какие из них я посетил, а какие нет. Чтобы выбрать следующий для посещения, я вычисляю угол (арктан) между двумя точками и посещаю следующую в порядке против часовой стрелки.
Ниже приведены скриншоты пройденных мной случаев и случаев Я терплю неудачу.
Формат ввода: Каждый тестовый пример состоит из нескольких строк. Первая строка содержит два целых числа, 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 целых чисел, представляющих контур, соответствующий краю грани. Порядок граней не важен, но последовательные вершины на ребре грани должны быть смежными.
[code]#include 

using namespace std;

#define _ ios_base::sync_with_stdio(0);cin.tie(0);
#define rep(i,x,n) for(int i=x;i=x;i--)
#define forr(v) for(auto& x: v)
#define all(a) (a).begin(), (a).end()
#define endl '\n'
#define ff first
#define ss second
#define pb push_back

typedef long long ll;
typedef pair ii;
typedef vector vi;
typedef vector vl;

const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3fll;

void DBG() {
cerr 

Подробнее здесь: [url]https://stackoverflow.com/questions/78343772/finding-faces-on-a-planar-graph-c[/url]