HackerEarth Buggy Bot problem solution

In this HackerEarth Buggy Bot problem solution, Alice finally finished her CS assignment and programmed her robot to explore a directed graph G with n nodes (numbered 1 through n) and m edges.

Alice programmed the robot with a series of k instructions. The robot will attempt to execute one instruction per second in the given order; it won’t repeat any instruction or return to an instruction it didn’t execute. Each instruction is of the form “if the robot is currently at node x, it will move to node y”. Note that if the robot is not currently at node x, it will ignore such an instruction. The robot is initially located at node 1.

Unfortunately, the robot is a bit buggy — at one moment in time, it can move from its current node to an arbitrary neighboring node (a node to which an edge leads from the current node). Note that this bug could have happened before any instructions, between any two instructions, or after all instructions; however, it couldn’t have happened multiple times. It is also possible that this bug did not happen at all.

Alice is having trouble debugging the robot, and would like your help to determine all nodes where the robot could be located at the end.

HackerEarth Buggy Bot problem solution.

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 100010, MAXM = 1000010, MAXK = 1000010;

int n, m, k, ia[MAXK], ib[MAXK], pos[MAXK], ee[MAXN];
set<int> graph[MAXN], tmp[MAXN], ans;

int main() {
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 0, a, b; i < m; i++) {
        scanf("%d%d", &a, &b);
        graph[a].insert(b);
    }

    for (int i = 0; i < k; i++) {
        scanf("%d%d", ia+i, ib+i);
    }

    pos[0] = 1;
    int cp = 1;
    for (int i = 0; i < k; i++) {
        if (cp == ia[i]) cp = ib[i];
        pos[i+1] = cp;
    }

    for (int i = 1; i <= n; i++) {
        ee[i] = i;
    }

    ans.insert(pos[k]);
    for (int i = k-1; i >= -1; i--) {
        int cnode = pos[i+1];
        for (int j : graph[cnode]) {
            ans.insert(ee[j]);
            tmp[j].insert(cnode);
        }
        graph[cnode].clear();

        if (i >= 0) {
            ee[ia[i]] = ee[ib[i]];
            for (int j : tmp[ia[i]]) {
                graph[j].insert(ia[i]);
            }
            tmp[ia[i]].clear();
        }
    }

    printf("%dn", ans.size());
    vector<int> xx(ans.begin(), ans.end());
    sort(xx.begin(), xx.end());
    for (int i = 0; i < ans.size(); i++) {
        printf("%d%c", xx[i], " n"[i == ans.size() - 1]);
    }
}

coding problems solutions