I’m working on an algorithms assignment at my college, which involves finding the vertices that belong to the face of a strictly planar and connected graph. However, I’ve encountered an issue with one of the test cases and I’m not sure how to resolve it. I’m finding one extra face than I should with my current method of visiting the vertices/edges. Could someone give me a hint?

This is my code.

I’m correctly identifying the faces in two test cases I have access to. However, depending on where the starting point is and where it’s connected, for instance, I find one extra face, which is incorrect. How can I fix this?

My logic for visiting and finding all the faces was to transform each edge into two directed ones, keeping track of which ones I’ve visited or not. To choose the next one to visit, I calculate the angle (arctan) between two points and visit the next one in counterclockwise order.

Below are the screenshots of the cases I pass and the cases I fail.

Input Format: Each test case consists of several lines. The first line contains two integers, N and M, representing respectively the number of vertices and edges of the input graph G. It is guaranteed that G is connected, 1 ≤ N, M ≤ 10^5, and V(G) = {1, 2, . . . , N}. The i-th line of the input starts with two real numbers xi, yi, representing the coordinates of vertex i in the Cartesian plane; it is guaranteed that −10^4 ≤ xi, yi ≤ 10^4. In the same line, we have a positive integer di, representing the degree of vertex i. Still on the same line, we have di integers between 1 and N, each corresponding to a neighbor of i; it is guaranteed that a vertex is not a neighbor of itself.

Output Format: The first line of the output contains an integer F, which should be equal to the number of faces of G. The next F lines should correspond to the F faces of G; each line starts with an integer si, representing the size of the i-th face of G; then there are si integers, representing the circuit corresponding to the edge of the face. The order of the faces is not important, but consecutive vertices on the edge of the face should be adjacent.

#include <bits/stdc++.h>

using namespace std;

#define _ ios_base::sync_with_stdio(0);cin.tie(0);
#define rep(i,x,n) for(int i=x;i<n;i++)
#define repr(i,n,x) for(int i=n;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<int,int> ii;
typedef vector<int> vi;
typedef vector<ll> vl;

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

void DBG() {
    cerr << "]" << endl;
}

void DBGC() {
    cerr << "]" << endl;
}

template<class H, class... T> void DBG(H h, T... t) {
    cerr << to_string(h);
    if(sizeof...(t)) cerr << ", ";
    DBG(t...);
}

template<class H, class... T> void DBGC(H h, T... t) {
    for(auto& x: h) cerr << x << " ";
    if(sizeof...(t)) cerr << "], [ ";
    DBGC(t...);
}

#ifndef _DEBUG
#define dbg(...) cerr << "[" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__)
#define dbgc(...) cerr << "["<< #__VA_ARGS__ << "]: [ "; DBGC(__VA_ARGS__) 
#else
#define dbg(...) 0
#define dbgc(...) 0
#endif
/*
double originDitance(int a){
    return sqrt(a.x*a.x + a.y*a.y);
}

double distance(int a, int b){
    double x = (a.x - b.x), y = (a.y - b.y);
    return sqrt(x*x + y*y);
}

double inclination(int p){
    return atan2(p.y, p.x);
}

int curve(int a, int b, int c){
    double v = a.x*(b.y-c.y) + b.x*(c.y-a.y) + c.x*(a.y-b.y);
    if(v < 0) return -1; //esquerda
    if(v > 0) return 1; //direita
    return 0;
}
*/

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
my answer

In the first test, my code is correct.

second test
my answer

In the second one as well.

third test
my answer – wrong

In the third one, it’s wrong. It identifies one extra face.

What should I do?