Find the symetry axis of a graph https://cw.felk.cvut.cz/courses/a4b33alg/task.php?task=videocard

GraphSymetry.cpp

// TASK: https://cw.felk.cvut.cz/courses/a4b33alg/task.php?task=videocard

#include <vector>
#include <cstdio>
#include <queue>
#include <algorithm>

using namespace std;

#if defined(WIN32) && !defined(UNIX)

int getchar_unlocked() { return getchar(); }

#elif defined(UNIX) && !defined(WIN32)
/* Do linux stuff */
#else
/* Error, both can't be defined or undefined same time */
#endif

typedef struct node {
    int content;
    vector<node *> children;
    bool candidate;

    //bool winner;
    template<typename T>
    inline bool operator()(const T *a, const T *b) const { return (*a).content < (*b).content; }
} node_t;

vector<node_t *> nodes;
vector<int> results;
int nodes_count, connections_count;

static inline bool parse_number(int *result) {
    int c = getchar_unlocked();
    switch (c) {
        case '0':
            *result = 0;
            return true;
        case '1':
            *result = 1;
            return true;
        case '2':
            *result = 2;
            return true;
        case '3':
            *result = 3;
            return true;
        case '4':
            *result = 4;
            return true;
        case '5':
            *result = 5;
            return true;
        case '6':
            *result = 6;
            return true;
        case '7':
            *result = 7;
            return true;
        case '8':
            *result = 8;
            return true;
        case '9':
            *result = 9;
            return true;
        default:
            return false;
    }
}

bool is_result(node_t *node) {
    node_t *left_child = node->children[0];
    node_t *right_child = node->children[1];


    if (left_child->children.size() != right_child->children.size()) return false;

    deque<node_t *> left;
    deque<node_t *> right;
    left.push_front(left_child);
    right.push_front(right_child);

    //visited histogram
    bool visited[nodes_count + 1] = {false};
    visited[node->content] = true;

    while (!left.empty() && !right.empty()) {
        int countness[connections_count + 1] = {0};
        int problems = 0;

        sort(left.begin(), left.end());
        sort(right.begin(), right.end());
        int i, j;
        i = j = 0;
        int left_size = left.size(); // velikost levé fronty pro danou fázi
        int right_size = right.size(); // velikost pravé fronty pro danou fázi

        // spracování front BFS
        while (i < left_size || j < right_size) {

            // =====
            if (i < left_size && j < right_size)
                if (left[i]->content == right[j]->content && left[i]->candidate) {
                    results.push_back(left[i]->content); // tento uzel také patří do osy souměrnosti
                    visited[left[i]->content] = true;
                    i++;
                    j++;
                    continue;
                }

            // Spracování levé fronty
            // kolik připojení má levý uzel - pokud jsem to již nepočítal
            if (i < left_size)
                if (!visited[left[i]->content]) {
                    for (int k = 0; k < left[i]->children.size(); ++k) {
                        node_t *tmp = left[i]->children[k];

                        // nenavštívený přidej do fronty
                        if (!visited[tmp->content]) {
                            countness[tmp->children.size()]++; //zaznamenání do histogramu
                            if (countness[tmp->children.size()] == 1) problems++;
                            left.push_back(tmp);
                        }
                    }
                }

            //Spracování pravé fronty
            // TODO kolik připojení má pravý uzel - pokud jsem to již nepočítal
            if (j < right_size)
                if (!visited[right[j]->content]) {
                    for (int k = 0; k < right[j]->children.size(); ++k) {
                        node_t *tmp = right[j]->children[k];
                        // nenavštívený přidej do fronty
                        if (!visited[tmp->content]) {
                            countness[tmp->children.size()]--; //zaznamenání do histogramu
                            if (countness[tmp->children.size()] == 0) problems--;
                            right.push_back(tmp);
                        }
                    }
                }

            // označ zkoumané uzly za navštívené
            if (i < left_size)
                visited[left[i]->content] = true;

            if (j < right_size)
                visited[right[j]->content] = true;

            // <<<<<< prvek levé fronty je menší než pravé fronty
            if (j >= right_size || (i < left_size && left[i]->content < right[j]->content)) {
                i++;
            }

                // >>>>>> prvek levé fronty je menší než pravé fronty
            else if (i >= left_size || (j < right_size && left[i]->content > right[j]->content)) {
                j++;
            }
        }

        // zlikvidovat zytek staré fronty
        left.erase(left.begin(), left.begin() + left_size);
        right.erase(right.begin(), right.begin() + right_size);


        // po zracování levých a pravých uzlů se musí shodovat četnosti jejich potomků
        if (problems != 0) return false;
    }

    return left.empty() && right.empty();
}

int main() {
    int res = scanf("%d %d ", &nodes_count, &connections_count);
    if (res != 2) return 1;

    // init nodes list
    nodes.reserve(nodes_count);
    for (int j = 0; j < nodes_count; ++j) {
        node_t *tmp = new node_t;
        tmp->content = j + 1;
        tmp->candidate = true;
        nodes[j] = tmp;
    }


    for (int i = 0; i < connections_count; ++i) {
        int from = 0;
        int to = 0;

        //TODO Getchar
        scanf("%d %d", &from, &to);

        //edge parsed
        from -= 1;
        to -= 1;

        nodes[from]->children.push_back(nodes[to]);
        nodes[to]->children.push_back(nodes[from]);

        if (nodes[from]->children.size() > 2)
            nodes[from]->candidate = false;

        if (nodes[to]->children.size() > 2)
            nodes[to]->candidate = false;
    }

    for (int i = 0; i < nodes_count; ++i) {
        if (nodes[i]->candidate) {
            if (is_result(nodes[i])) {
                results.push_back(nodes[i]->content);
                break; // all results found
            }
        }
    }

    //results found
    sort(results.begin(), results.end());
    for (int i = 0; i < results.size() && i < 100; ++i) {
        printf("%d ", results[i]);
    }

    printf("\n");

    //freeing section
    for (int j = 0; j < nodes_count; ++j) {
        delete nodes[j];
    }
    return 0;
}