marten

marten.cpp

#include <iostream>
#include <vector>
#include <algorithm>

class Vertex {
public:
    // Vertex id in vertexes.
    int id;
    // Index of vertex begin edge (first).
    int idx;
    // Index of vertex end edge (last + 1).
    int end;
    // Edges left to explore.
    int eleft;
    // Set to true when vertex has been seen.
    bool seen;
};

class Edge {
public:
    // Edge from.
    int a;
    // Edge to.
    int b;
};

void exit_result(bool yes) {
    std::cout << (yes? "YES": "NO");
    exit(0);
}

int main() {
    // Read input edges.
    std::ios_base::sync_with_stdio(false);
    int n, e;
    std::cin >> n >> e;
    std::vector<Vertex> vertexes(n);
    std::vector<Edge> edges(e * 2);
    for (int i = 0; i < e; i++) {
        int a, b;
        std::cin >> a >> b;
        edges[i * 2 + 0] = Edge{a, b};
        edges[i * 2 + 1] = Edge{b, a};
    }
    // Sort edges [a, b].
    auto cmp_edges = [](const Edge& x, const Edge& y) -> bool {
        return std::make_pair(x.a, x.b) < std::make_pair(y.a, y.b);
    };
    std::sort(edges.begin(), edges.end(), cmp_edges);
    // Group and index all edge segments.
    // We also count edges left.
    auto set_vend = [](Vertex& v, int end) {
        v.end = end;
        v.eleft = end - v.idx;
    };
    for (int last = -1, i = 0; i < edges.size(); i++) {
        auto& edge = edges[i];
        if (edge.a != last) {
            if (last >= 0) {
                set_vend(vertexes[last], i);
            }
            vertexes[edge.a].id = edge.a;
            vertexes[edge.a].idx = i;
            last = edge.a;
        }
    }
    set_vend(vertexes.back(), edges.size());
    // We stream new vertexes unto a stack.
    std::vector<Vertex*> stk;
    auto read_vertex = [&stk, &vertexes, &edges]() {
        int id;
        std::cin >> id;
        if (std::cin.eof()) {
            exit_result(false);
        }
        if (id < 0 || id >= vertexes.size()) {
            exit_result(false);
        }
        auto& v = vertexes[id];
        // Seen barrier.
        if (v.seen) {
            exit_result(false);
        }
        v.seen = true;
        // Reduce edges left for all connected nodes.
        for (int i = v.idx; i < v.end; i++) {
            vertexes[edges[i].b].eleft--;
        }
        stk.emplace_back(&v);
    };
    // Read initial (start) vertex.
    read_vertex();
    // As long as we have a stack the initial vertex has not been fully explored.
    while (stk.size() > 0) {
        // Get parent vertex.
        auto& pv = *stk.back();
        if (pv.eleft <= 0) {
            // Exploring this vertex is complete, no edges left.
            stk.pop_back();
            continue;
        }
        // Read child vertex.
        read_vertex();
        auto& cv = *stk.back();
        // Binary search, find path from parent to child.
        if (!std::binary_search(edges.begin() + pv.idx, edges.begin() + pv.end, Edge{pv.id, cv.id}, cmp_edges)) {
            // No such link, fail.
            exit_result(false);
        }
    }
    // We found a prefix that was valid.
    // Read one more to determine if prefix is full graph.
    {
        int i;
        std::cin >> i;
        exit_result(std::cin.fail() && std::cin.eof());
    }
}