在平面图上查找面

Question

我正在大学做一项算法作业，其中涉及查找属于严格平面连通图的面的顶点。但是，我遇到了其中一个测试用例的问题，并且不知道如何解决它。我发现比我当前访问顶点/边的方法应该多的一张面。有人可以给我提示吗？

我正确识别了我可以访问的两个测试用例中的面孔。然而，根据起点的位置和连接的位置，例如，我发现了一张额外的面，这是不正确的。我该如何解决这个问题？

我访问和查找所有面孔的逻辑是将每条边转换为两个有向边，记录我访问过或未访问过哪些边。为了选择下一个要访问的点，我计算两点之间的角度（反正切）并按逆时针顺序访问下一个点。

我使用反正切循环对每个顶点连接到其邻居的边进行排序。这样我就可以逆时针排列边缘了。

示例：

在这张图片中，我有任何平面和连通图。

在另一张图像中，我有相同的图形，但以我的代码看到的方式，一个边去，另一个边返回，而不是原始边。也就是说，我直接边缘并复制它。

在另一张图像中，我有任何顶点连接到其他四个顶点。使用我的代码的顺序，第一条边将是（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, . 。 。 ，N}。输入的第i行以两个实数xi,yi开头，表示顶点i在笛卡尔平面中的坐标；保证−10^4 ≤ xi, yi ≤ 10^4。在同一行中，我们有一个正整数di，表示顶点i的度数。仍然在同一行，我们有 1 到 N 之间的 di 个整数，每个整数对应于 i 的一个邻居；保证顶点不是其自身的邻居。

输出格式：输出的第一行包含一个整数F，它应该等于G的面数。接下来的F行应该对应G的F个面；每行以整数Si开头，代表G的第i面的大小；然后是Si个整数，代表面的边缘对应的电路。面的顺序并不重要，但面边缘上的连续顶点应该相邻。

#include <bits/stdc++.h>

using namespace std;

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

typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef vector<ll> vl;

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

vector<int> face;
vector<vector<int>> faces;

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

vector<int> sort_connections(int i, vector<int>& connections, vector<pair<double, double>> 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 << faces.size() << endl;
    for(int i = 0; i < faces.size(); i++){
        cout << faces[i].size() << " ";
        for(int j = 0;  j < faces[i].size(); j++){
            cout << faces[i][j]+1 << " ";
        }
        cout << endl;
    }
}

void dfs(int b, int i, int j, int n, vector<vector<int>>& graph, vector<vector<bool>>& visited, vector<pair<double, double>>& positions){

    visited[i][j] = true;

    if (b == n) {
        face.pb(b);
        faces.push_back(face);
        face.clear();
        return;
    }

    int k = 0;
    while(true){
        if(graph[n][k] == i){
            k++; 
            break;
        }
        k++;
    }

    for(; k <= graph[n].size(); k++){
        if(k == graph[n].size()) k = 0;
        if(!visited[n][k]) break;
    }
            
    face.pb(n);
    dfs(b, n, k, graph[n][k], graph, visited, positions);
}

int main (){

    int n, m; cin >> n >> m;

    vector<vector<int>> graph(n);
    vector<vector<bool>> visited(n);
    vector<pair<double, double>> positions(n); 

    for(int i = 0; i < n; i++){
        double x, y; cin >> x >> y;

        pair<double, double> 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 

第三个，错了。它识别出一张额外的面孔。

我该怎么办？

Answer 1

这是一个有趣的算法问题。我目前无法提供解决方案，但是通过绘制第三个测试用例的图表，错误是什么就变得非常明显了：

在上图中，顶点和面根据输入和预期输出数据进行编号。

您的程序正确识别了面 2-6，但是它计算了两次 6，第二次将顶点 1 添加到其中，并且也无法正确识别面 1，将其视为由 1,3,4,2 形成的整个正方形。