Editorial for Maze

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.

Türkçe

Soruyu incelediğimizde soruda istenenin verilen graph'in bir Eulerian path olup olmadığını bulmak. Bunun için de aşağıdaki iki sağlayıp sağlamadığına bakmamız gerekli.

  • Tek sayıda edge'i olan node'ların sayısının 2 ya da 0 olması.
  • Graph'taki tüm node'ların birbirine bağlı olması. (Graph'in tek bir parçadan oluşması)

Bu koşulları \(O(\mathbf{N+M})\) (\(\mathbf{M}\) kavşak sayısı) sürede kontrol edebiliriz.

English

When we analyze the problem, what we are asked is whether the graph is an Eulerian path or not. To check this, we need to check the following two conditions:

  • The number of nodes that have an odd number of edges must be either 2 or 0.
  • All of the nodes in the graph must be connected. (Graph should consist of one piece.)

We can do these checks in \(O(\mathbf{N+M})\) (\(\mathbf{M}\) number of intersections) time.

#include <bits/stdc++.h>
using namespace std;

map<int, int> M;

int getIndex(int a){
    if(M.count(a) == 0) M[a] = M.size();
    return M[a];
}

bool f(vector<int>& cnt, vector<vector<int>>& edges){
    int n = cnt.size();
    int odd = 0;
    for(int i = 0; i < n; ++i) if(cnt[i] % 2 != 0) ++odd;
    if(odd > 2) return false;
    vector<bool> used(n, false);
    int components = 0;
    for(int i = 0; i < n; ++i)
        if(cnt[i] != 0 && !used[i]){
            ++components;
            queue<int> q;
            q.push(i);
            used[i] = true;
            while(!q.empty()){
                int a = q.front();
                q.pop();
                for(int b : edges[a])
                    if(!used[b]){
                        used[b] = true;
                        q.push(b);
                    }
            }
        }

    return components == 1;
}

int main(){
    int n;
    cin >> n;
    int amount = 2*n;
    vector<int> cnt(amount, 0);
    vector<vector<int>> edges(amount);
    for(int i = 0; i < n; ++i){
        int a, b;
        cin >> a >> b;
        a = getIndex(a);
        b = getIndex(b);
        ++cnt[a];
        ++cnt[b];
        edges[a].push_back(b);
        edges[b].push_back(a);
    }

    cout << (f(cnt, edges) ? "YES" : "NO") << endl; 
}